J. Отрезки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Имеется прямая, покрашенная в белый цвет. На нее добавляют 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
Примечание

В первом примере после добавления двух первых отрезков будет две компоненты, так как добавленные отрезки не пересекаются. После этого добавится третий отрезок, который пересекается с первым и касается второго в точке 4 (по условию такие отрезки принадлежат одной компоненте). Поэтому после добавления третьего отрезка количество компонент связности из черных отрезков станет равно 1.