머나먼 행성에서 이상한 식물이 규칙적으로 자라는 것을 발견했습니다. 이 식물은 직사각형으로 생겼으며 맨 처음 1의 높이값을 가집니다. 매일마다 하나의 식물이 새로 자라납니다. 이 식물은 바로 전날의 식물보다 1만큼 더 높습니다. (이미 생성된 식물은 성장하지 않습니다)

식물이 매일매일 하나씩 생성될때 이 식물들의 모서리의 교차점에 꽃이 생성됩니다.(간단히 말해 사각형끼리의 교점) 식물은 기존의 식물과 교차할수도, 하지 않을수도 있습니다. 하지 않을경우 꽃은 생성되지 않습니다.

매일 몇개의 꽃이 생성되는지 출력하세요.

입력

• 첫번째 줄에 N, 관찰할 날짜의 수를 입력합니다.
• 각각의 날짜마다 자라날 식물의 좌표를 입력합니다. 좌표는 L과 R로 구성되어 있으며 L에는 왼쪽끝 좌표, R에는 오른쪽 끝 좌표를 대입합니다.

출력

입출력 예 -- Hint & 상세설명

input  

4(4일을 관찰합니다.) 
1 4 (1일째 좌표 1,4에서 식물이 생성됩니다. 높이는 1입니다.) 
3 7 (2일째 좌표 3,7에서 식물이 생성됩니다. 높이는 2입니다.) 
1 6  
2 6  

output  

0 (첫째날은 식물이 하나밖에 없으므로 피어난 꽃이 없습니다.) 
1 (둘째날에 두 식물이 교차해서 하나의 꽃이 피어났습니다.) 
2  

input  

5  
1 3  
3 5  
3 9  
2 4  
3 8  

output  

0  
0  
0  
3  

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 on the next page.

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

입력

• The first line contains an integer N (1 ≤ N ≤ 100000), the number of days.
• Each of the following N lines contains two integers L and R (1 ≤ L < R ≤ 100000), the coordinates of the stems of a plant.

출력

입출력 예

input 

4 
1 4 
3 7 
1 6 
2 6 

output 

0 
1 
1 
2 

input 

5 
1 3 
3 5 
3 9 
2 4 
3 8 

output 

0 
0 
0 
3 
2 

출처:coci/2008-2009/regional
번역:ironamor