Problem
Es gibt eine gerade, weiße Farbe. Es werden nacheinander n schwarze Abschnitte hinzugefügt.
Bestimmen Sie nach jedem Hinzufügen der Linie die Anzahl der Konnektivitätskomponenten aus schwarzen Linien (d. H. Die Anzahl der schwarzen Linien in der Vereinigung).
Bedenken Sie insbesondere, dass, wenn eine Linie am Punkt x endet und die andere Linie am Punkt x beginnt, diese beiden Linien in derselben Konnektivitätskomponente liegen.
Eingabe
Die erste Zeile folgt einer ganzen Zahl n (1 ≤ n ≤ 200 000) — Anzahl der Segmente.
Die erste der folgenden n Zeilen enthält zwei ganze Zahlen li und ri (1 ≤ li < ri ≤ 109) — die Koordinaten des linken und rechten Endes der Linie Nummer i. Die Linien werden in der Reihenfolge aufgelistet, in der sie der weißen Linie hinzugefügt werden.
Ausgabe
Geben Sie n ganze Zahlen aus — die Anzahl der Konnektivitätskomponenten aus den schwarzen Linien aus, nachdem Sie jedes Segment hinzugefügt haben.
Beispiele
| № |
Eingabe |
Ausgabe |
| 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 |