Segments

Description:

Input:

The first line contains a single integer n (1 ≤ n ≤ 200 000) — the number of segments.

The i-th of the next n lines contains two integers l_i and r_i (1 ≤ l_i < r_i ≤ 10⁹) — the coordinates of the left and the right ends of the i-th segment. The segments are listed in the order they are added on the white line.

Output:

Print n integers — the number of connected components of black segments after each segment is added.

Sample Input:

3
1 3
4 5
2 4

Sample Output:

1 2 1 

Sample Input:

9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90

Sample Output:

1 2 3 4 5 4 3 2 1 

Note:

In the first example there are two components after the addition of the first two segments, because these segments do not intersect. The third added segment intersects the left segment and touches the right segment at the point 4 (these segments belong to the same component, according to the statements). Thus the number of connected components of black segments is equal to 1 after that.