Description

On a distant planet, a strange plant with two stems was discovered.

Each plant on the planet can be described by $3$ numbers: the $x$ coordinates of stems $L$ and $R$, and the height $H$ at which the two stems are connected. The picture below shows a plant with $L = 2$, $R = 5$, $H = 4$:

Every day, new plants grow on this planet. A plant that grows on day $1$ has height $1$, and every plant that grows on each following day is taller than the plants that grew on the previous day.

When a stem of one plant intersects the horizontal segment that connects the two stems of another plant, a small flower will grow at the intersection point (unless there is already a flower at that point). There is one exception: if the intersection forms a "T" shape, that is, when a stem of one plant overlaps with a stem of another plant, then no flower will grow at the intersection point. Some examples are shown below:

Given the coordinates of all plants, find the number of flowers that grow each day.

Input Format

The first line contains a positive integer $n$, the number of days.

In the next $n$ lines, each line contains two integers $L_i$ and $R_i$, the coordinates of the two stems of the plant that grows on that day.

Output Format

Output $n$ lines. Each line contains a positive integer, in order, representing the number of flowers that grow on day $n$.

4
1 4
3 7
1 6
2 6 

0
1
1
2 

5
1 3
3 5
3 9
2 4
3 8 

0
0
0
3
2

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le L_i < R_i \le 10^5$.

Notes

• This problem is worth $130$ points in total.
• This problem is translated from COCI2008-2009 CRCI2008-2009 CVJETICI. The main translation was done by
  https://www.luogu.com.cn/user/219791

Translated by ChatGPT 5