segments
Problem
Il y a une ligne droite, peinte en blanc. n segments noirs y sont ajoutés un par un.
Déterminez le nombre de segments noirs connectés (c'est-à-dire le nombre de segments noirs dans l'union) après chaque ajout de segment.
En particulier, considérez que si un segment se termine au point x et qu'un autre segment commence au point x, alors ces deux segments se trouvent dans le même composant connexe.
Entrée
La première ligne est un entier n (1 ≤ n ≤ 200 000) — nombre de segments.
i-ième des n lignes suivantes contient deux entiers li et ri (1 ≤ li < ri ≤ 109) — coordonnées des extrémités gauche et droite du segment numéro i. Les segments sont répertoriés dans l'ordre dans lequel ils ont été ajoutés à la ligne blanche.
Sortie
Imprimer n entiers — le nombre de composants connectés à partir de segments noirs après chaque ajout d'un segment.
Exemples
| # |
Entrée |
Sortie |
| 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 |