Segmenti
Problem
C'è una linea retta, dipinta di bianco. n segmenti neri vengono aggiunti ad esso uno per uno.
Determina il numero di segmenti neri connessi (ovvero il numero di segmenti neri nell'unione) dopo ogni aggiunta di segmenti.
In particolare, considera che se un segmento termina nel punto x e un altro segmento inizia nel punto x, allora questi due segmenti giacciono nella stessa componente connessa.
Input
La prima riga è un numero intero n (1 ≤ n ≤ 200 000) — numero di segmenti.
i-esima delle successive n righe contiene due numeri interi li e ri (1 ≤ li < ri ≤ 109) — coordinate delle estremità sinistra e destra del segmento numero i. I segmenti sono elencati nell'ordine in cui sono stati aggiunti alla linea bianca.
Uscita
Stampa n numeri interi — il numero di componenti connessi dai segmenti neri dopo ogni aggiunta di un segmento.
Esempi
| # |
Input |
Uscita |
| 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 |