eolymp
Змагання

Дерево Фенвика

Зірки

Астрономи часто вивчають зоряні карти, де зірки подано точками на площині, і кожна з них має свої декартові координати. Рівнем зірки назвемо кількість зірок, які знаходяться не вище і не правіше від неї. Астрономи хочуть взнати розподіл рівнів зірок.

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 секунда
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
5
1 1
5 1
7 1
3 3
5 5
Вихідні дані #1
1
2
1
1
0
Автор Павло Залецький
Джерело 1999 III Командний Студентський Чемпіонат Уралу, Єкатеринбург, Березень 19 - 20, Задача А