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 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 \le N \le 100\,000)~, the number of days. Each of the following ~N~ lines contains two integers ~L~ and ~R~ ~(1 \le L < R \le 100\,000)~, the coordinates of the stems of a plant.
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