Đoạn thẳng

Trên một trục số ban đầu được tô màu trắng. Người ta lần lượt thêm vào $n$ đoạn thẳng màu đen.

Sau mỗi lần thêm một đoạn, hãy xác định số thành phần liên thông của các đoạn đen — tức là số đoạn thẳng rời nhau trong hợp của tất cả các đoạn đen đã thêm cho tới thời điểm đó.

Lưu ý: nếu một đoạn kết thúc tại điểm $x$ và một đoạn khác bắt đầu tại điểm $x$, thì hai đoạn này được coi là thuộc cùng một thành phần liên thông (hai đoạn chạm nhau tại một điểm cũng được tính là liên thông).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ — số đoạn thẳng.
• Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i$ và $r_i$ — tọa độ đầu trái và đầu phải của đoạn thứ $i$. Các đoạn được liệt kê theo đúng thứ tự chúng được thêm vào.

Dữ liệu ra

In ra $n$ số nguyên — số thành phần liên thông của các đoạn đen sau mỗi lần thêm đoạn.

Ràng buộc

• $1\le n\le 200000$
• $1\le l_i<r_i\le {10}^9$

Ví dụ