Một khu vực lớn trên dãy Alps vừa trở thành khu bảo tồn. Ban đầu không có con cáo nào; mỗi ngày có thêm một con cáo đến. Nhà sinh vật học Simona quan tâm đến số gia đình cáo tại từng thời điểm.

Lãnh thổ săn mồi của cáo \(i\) là đoạn \([L_i,R_i]\), với \(L_i<R_i\). Các đoạn có thể giao nhau hoặc chứa nhau. Hai cáo \(i,j\) là họ hàng trực tiếp nếu lãnh thổ này chứa lãnh thổ kia:

hoặc

Hai cáo thuộc cùng một gia đình khi chúng là họ hàng trực tiếp hoặc được nối bởi một chuỗi quan hệ họ hàng trực tiếp. Chính xác hơn, tồn tại dãy cáo \(c_0,c_1,\ldots,c_{m-1}\) với \(c_0=a\), \(c_{m-1}=b\), và \(c_i,c_{i+1}\) là họ hàng trực tiếp với mọi \(0\le i<m-1\).

Cáo \(i\) đến vào ngày \(i\) và ở lại vĩnh viễn với lãnh thổ \([L_i,R_i]\). Sau mỗi ngày, hãy tính số gia đình sau khi cáo mới đến.

Dữ liệu vào

Dòng đầu chứa \(N\).

\(N\) dòng tiếp theo, dòng \(i\) chứa \(L_i,R_i\).

Dữ liệu ra

In \(N\) dòng. Dòng \(i\) chứa số gia đình cáo sau khi cáo \(i\) đến.

Ràng buộc

• \(1\le N\le100\,000\).
• \(0\le L_i<R_i\le200\,000\).
• Không có cặp \((L_i,R_i)\) nào xuất hiện hai lần.

Phân nhóm

1. \(10\) điểm: \(N\le100\).
2. \(15\) điểm: \(N\le2000\).
3. \(16\) điểm: \(R_i-L_i\le2\).
4. \(23\) điểm: \(L_i<L_{i+1}\).
5. \(36\) điểm: không có ràng buộc thêm.

Ví dụ

4
1 4
3 6
3 4
6 7

1
2
1
2

6
0 1
1 2
2 3
3 4
4 5
2 4

1
2
3
4
5
4

5
0 5
1 4
2 7
3 6
4 5

1
1
2
2
1

Nguồn

EGOI 2026 - Ngày 2, Fox Families.

Đề bài EGOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).