On a faraway planet, strange plants with two stems can be found. Every plant on the planet can be described by three numbers: the ~x~-coordinates of the stems ~L~ and ~R~, and the height ~H~ at which the stems are connect. The image depicts a plant with ~L = 2~, ~R = 5~ and ~H = 4~.

Every day a new plant grows on the planet. The plant that grows on day ~1~ is of height ~1~, and every subsequent plant is one higher than the previous one.

When a stem of a new plant intersects the horizontal segment of another plant, a small flower grows (if one wasn't there already). If segments merely touch in a point, a flower will not grow there. The following images are a visualization of the first example.

Write a program that, given the coordinates of all plants, calculates the number of new flower every day.

Input

The first line contains an integer ~N~ ~(1 \leq N \leq 100 000)~, the number of days.

Each of the following ~N~ lines contains two integers ~L~ and ~R~ ~(1 \leq L < R \leq 100 000)~, the coordinates of the stems of a plant.

Output

Output ~N~ lines, the number of new flowers after each plant grows.

Sample Input 1

4
1 4
3 7
1 6
2 6

Sample Output 1

0
1
1
2

Sample Input 2

5
1 3
3 5
3 9
2 4
3 8

Sample Output 2

0
0
0
3
2