LRH Plants

A gardener has created plants made of two vertical stems and one horizontal segment. A plant is described by the x-coordinates L and R of its stems and by its height H. The figure below shows a plant with L = 2, R = 5, and H = 4.

The gardener plants one new plant each day. The plant planted on day 1 has height 1, and each later plant is exactly 1 taller than the plant from the previous day.

A flower blooms at a point where a stem of the newly planted plant crosses the horizontal segment of another plant. If a flower has already bloomed at that point, no additional flower blooms there. If the two parts only touch at an endpoint, no flower blooms.

The next figure illustrates one possible arrangement.

Given all plant coordinates in planting order, compute how many flowers bloom on each day.

The first line contains the number of planting days N (1 <= N <= 100000).

Each of the next N lines contains two integers L and R, the x-coordinates of the two stems of the plant planted that day (1 <= L < R <= 100000).

Print N lines. The i-th line must contain the number of flowers that bloom on day i.