CVJETICI - Cvjetici

Giới hạn

• Thời gian: 0.406s
• Bộ nhớ: 1536MB
• Mã nguồn: 2000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 ≤ N ≤ 100 000), the number of days.

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

Output

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

Example

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

---

• Người up: racer
• Nguồn bài: COCI 2008/2009 - Croatian Regional