Имеется прямая, покрашенная в белый цвет. На нее добавляют n черных отрезков один за другим.
Определите количество компонент связности из черных отрезков (то есть количество черных отрезков в объединении) после каждого добавления отрезка.
В частности, считайте, что если один отрезок заканчивается в точке x, а другой отрезок начинается в точке x, то эти два отрезка лежат в одной компоненте связности.
В первой строке следует целое число n (1 ≤ n ≤ 200 000) — количество отрезков.
i-я из следующих n строк содержит два целых числа li и ri (1 ≤ li < ri ≤ 109) — координаты левого и правого концов отрезка номер i. Отрезки перечислены в порядке их добавления на белую прямую.
Выведите n целых чисел — количество компонент связности из черных отрезков после каждого добавления отрезка.
В первом примере после добавления двух первых отрезков будет две компоненты, так как добавленные отрезки не пересекаются. После этого добавится третий отрезок, который пересекается с первым и касается второго в точке 4 (по условию такие отрезки принадлежат одной компоненте). Поэтому после добавления третьего отрезка количество компонент связности из черных отрезков станет равно 1.
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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач