There is a straight line, painted white. n black segments are added to it one by one.
Determine the number of connected black segments (that is, the number of black segments in the union) after each segment addition.
In particular, consider that if one segment ends at point x and another segment begins at point x, then these two segments lie in the same connected component.
Input
The first line is an integer n (1 ≤ n ≤ 200 000) — number of segments.
i-th of the next n lines contains two integers li and ri (1 ≤ li < ri ≤ 109) — coordinates of the left and right ends of segment number i. The segments are listed in the order they were added to the white line.
Output
Print n integers — the number of connected components from black segments after each addition of a segment.
Examples
| # |
Input |
Output |
| 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 |