Problem
白く塗られた直線があります。 n 個の黒いセグメントが 1 つずつ追加されます。
各セグメントの追加後に、接続された黒セグメントの数 (つまり、ユニオン内の黒セグメントの数) を決定します。
特に、1 つのセグメントが点 x で終わり、別のセグメントが点 x で始まる場合、これら 2 つのセグメントは同じ連結成分にあると考えてください。
入力
最初の行は整数 n (1 ≤ n ≤ 200 000) — です。セグメント数。
次の n 行の i 番目には、2 つの整数 li と ri が含まれます (1 ≤ li < ri ≤ 109) —セグメント番号 i の左端と右端の座標。セグメントは、白線に追加された順序でリストされています。
出力
n 個の整数を表示 —セグメントを追加するたびに、黒いセグメントからの連結成分の数。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 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 |