Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Имеется прямая, покрашенная в белый цвет. На нее добавляют n черных отрезков один за другим.
Определите количество компонент связности из черных отрезков (то есть количество черных отрезков в объединении) после каждого добавления отрезка.
В частности, считайте, что если один отрезок заканчивается в точке x, а другой отрезок начинается в точке x, то эти два отрезка лежат в одной компоненте связности.
Входные данные
В первой строке следует целое число n (1 ≤ n ≤ 200 000) — количество отрезков.
i-я из следующих n строк содержит два целых числа li и ri (1 ≤ li < ri ≤ 109) — координаты левого и правого концов отрезка номер i. Отрезки перечислены в порядке их добавления на белую прямую.
Выходные данные
Выведите n целых чисел — количество компонент связности из черных отрезков после каждого добавления отрезка.
|
Ввод |
Вывод |
|
3
1 3
4 5
2 4
|
1 2 1 |
|
9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90
|
1 2 3 4 5 4 3 2 1 |
(с) Курбатов Е., 2018