Имеется прямая, покрашенная в белый цвет. На нее добавляют n черных отрезков один за другим.
Определите количество компонент связности из черных отрезков (то есть количество черных отрезков в объединении) после каждого добавления отрезка.
В частности, считайте, что если один отрезок заканчивается в точке x, а другой отрезок начинается в точке x, то эти два отрезка лежат в одной компоненте связности.
Выходные данные
Выведите n целых чисел — количество компонент связности из черных отрезков после каждого добавления отрезка.
Примечание
В первом примере после добавления двух первых отрезков будет две компоненты, так как добавленные отрезки не пересекаются. После этого добавится третий отрезок, который пересекается с первым и касается второго в точке 4 (по условию такие отрезки принадлежат одной компоненте). Поэтому после добавления третьего отрезка количество компонент связности из черных отрезков станет равно 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3
4 5
2 4
|
1 2 1
|
|
2
|
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
|