Segmentos
Problem
Há uma linha reta, pintada de branco. n segmentos pretos são adicionados a ele um por um.
Determine o número de segmentos pretos conectados (ou seja, o número de segmentos pretos na união) após cada adição de segmento.
Em particular, considere que se um segmento termina no ponto x e outro segmento começa no ponto x, então esses dois segmentos estão no mesmo componente conectado.
Entrada
A primeira linha é um inteiro n (1 ≤ n ≤ 200 000) — número de segmentos.
i-ésima das próximas n linhas contém dois inteiros li e ri (1 ≤ li < ri ≤ 109) — coordenadas das extremidades esquerda e direita do segmento número i. Os segmentos são listados na ordem em que foram adicionados à linha branca.
Saída
Imprime n inteiros — o número de componentes conectados de segmentos pretos após cada adição de um segmento.
Exemplos
| # |
Entrada |
Saída |
| 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 |