Problem
Hay una línea recta, pintada de blanco. Se le agregan n segmentos negros uno por uno.
Determine la cantidad de segmentos negros conectados (es decir, la cantidad de segmentos negros en la unión) después de cada adición de segmento.
En particular, considere que si un segmento termina en el punto x y otro segmento comienza en el punto x, entonces estos dos segmentos se encuentran en la misma componente conexa.
Entrada
La primera línea es un número entero n (1 ≤ n ≤ 200 000) — número de segmentos.
i-ésimo de las siguientes n líneas contiene dos enteros li y ri (1 ≤ li < ri ≤ 109) — coordenadas de los extremos izquierdo y derecho del segmento número i. Los segmentos se enumeran en el orden en que se agregaron a la línea blanca.
Salida
Imprimir n enteros — el número de componentes conectados de segmentos negros después de cada adición de un segmento.
Ejemplos
| # |
Entrada |
Salida |
| 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 |