Problem
Có một đường thẳng được sơn màu trắng. n phân đoạn màu đen được thêm vào từng cái một.
Xác định số đoạn màu đen được kết nối (nghĩa là số đoạn màu đen trong liên kết) sau mỗi lần thêm đoạn.
Cụ thể, hãy xem xét rằng nếu một đoạn kết thúc tại điểm x và một đoạn khác bắt đầu tại điểm x, thì hai đoạn này nằm trong cùng một thành phần được kết nối.
Đầu vào
Dòng đầu tiên là số nguyên n (1 ≤ n ≤ 200 000) — số lượng phân khúc.
i-th trong số n dòng tiếp theo chứa hai số nguyên li và ri (1 ≤ li < ri ≤ 109) — tọa độ hai đầu bên trái và bên phải của đoạn số i. Các phân đoạn được liệt kê theo thứ tự chúng được thêm vào dòng màu trắng.
Đầu ra
In ra n số nguyên — số lượng thành phần được kết nối từ các đoạn màu đen sau mỗi lần thêm một đoạn.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 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 |