Giáo sư Hà Phong của trường đại học Nevada vừa công bố một phát hiện khoa học mới về hành tinh XYZ. Công bố của ông đã cho thấy có tồn tại sự sống của một loài cây trên hành tinh XYZ. Sự tồn tại và phát triển của loại cây này rất kì lạ. Mỗi cây được lớn lên từ hai "mầm", hai "mầm" này sẽ đâm lên khỏi mặt đất với độ cao ~H~ vào một ngày nào đó và dừng lại ở đó không phát triển thêm nữa. Cây khi đâm lên khỏi mặt đất sẽ có dạng như một hình chữ nhật (xem Hình 1), hai cạnh bên được gọi là "vertical" cạnh bắc ngang được gọi là "horizontal". Mỗi cây trên hành tinh đó được biểu diễn bởi ba số: các tọa độ ~x~ của các "vertical" là ~L~ và ~R~, và độ cao ~H~.

Mỗi ngày có một cây mới mọc lên từ hành tinh. Mỗi cây mới mọc lên có chiều cao lớn hơn chiều cao của cây mọc lên ngày liền trước đó một đơn vị. Khi một cạnh "vertical" một cây mới giao với một cạnh "horizontal" một cây khác thì có một bông hoa tại điểm giao đó được nở ra với điều kiện giao điểm đó không phải là các đầu mút của cạnh "horizontal" và tại điểm đó chưa từng tồn tại bông hoa nào.

Yêu cầu: Cho biết tọa độ "vertical" của các cây mọc lên mỗi ngày, cây mọc lên trong ngày thứ nhất có chiều cao bằng 1. Hãy cho biết mỗi ngày có bao nhiêu bông hoa mới xuất hiện.

Dữ liệu vao:

• Dòng đầu tiên ghi một số nguyên ~n~ (1 ≤ ~n~ ≤ 100.000) là số ngày.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~L,R~ (1 ≤ ~L~ < ~R~ ≤ ~10^5~) là tọa độ các cạnh "vertical" của cây mọc lên vào ngày thứ ~i~.

Kết quả: Ghi ra ~n~ dòng, dòng thứ ~i~ là số bông hoa mới được nở ra trong ngày thứ ~i~.

Vi du:

INPUT 1

4 
1 4 
3 7 
1 6 
2 6

OUTPUT 1

0 
1
1 
2

INPUT 2

5 
1 3 
3 5 
3 9 
2 4
3 8

OUTPUT 2

0 
0
0 
3
2

Ràng buộc:

• Có 25% số test tương ứng 25% số điểm có ~n~ ≤ 5000, ~R~ ≤ 5000;
• Có 25% số test khác tương ứng 25% số điểm có ~n~ ≤ 5000, ~R~ ≤ ~10^6~;
• Có 25% số test khác tương ứng với 25% số điểm có ~n~ ≤ 50000,~R~ ≤ 250;
• 25% số test còn lại tương ứng 25% số điểm có ~n~ ≤ ~10^5~, ~R~ ≤ ~10^5~.