eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Звезды

Звезды

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Астрономы часто изучают звездные карты, где звезды представлены точками на плоскости, и каждая из них имеет свои декартовы координаты. Уровнем звезды назовем количество звезд, которое находится не выше и не правее от нее. Астрономы хотят знать распределение уровней звезд.

prb5619

Например, посмотрим на приведенную вверху карту. Уровень звезды номер 5 равен 3 (он формируется звездами с номерами 1, 2 и 4). Уровень звезд 2 и 4 равен 1. На этой карте только одна звезда имеет уровень 0, две звезды имеют уровень 1, одна звезда уровня 2, и одна звезда уровня 3.

Напишите программу, которая подсчитает количество звезд на каждом уровне заданной карты.

Входные данные

Первая строка содержит количество звезд n (1n15000). Следующие n строк описывают координаты звезд - два целых числа x и y в одной строке, 0x, y32000. В одной точке плоскости может находиться только одна звезда. Звезды перечислены в возрастающем порядке y координаты. Звезды с равной y координатой перечислены в порядке возрастания их x координаты.

Выходные данные

Вывести n строк, по одному числу в каждой из них. Первая строка должна содержать количество звезд уровня 0, вторая строка - количество звезд уровня 1 и так далее. Последняя строка содержит количество звезд уровня n - 1.

Пример

Входные данные #1
5
1 1
5 1
7 1
3 3
5 5
Выходные данные #1
1
2
1
1
0
Автор Павел Залецкий
Источник 1999 III Командный Студенческий Чемпионат Урала, Екатеринбург, Март 19 - 20, Задача А