PBCSEQ - Các đoạn nguyên

Giới hạn

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

Mirko có một tập hợp các đoạn nguyên. Đầu tiên, anh ấy lấy ra 1 đoạn bất kì. Sau đó thực hiện lấy các đoạn khác, sao cho: đoạn lấy ra nằm trong đoạn vừa được lấy trước nó. Mirko tiếp tục cho đến khi không tìm được đoạn thoả mãn nữa.

Yêu cầu

Tìm số đoạn lớn nhất có thể lấy ra.

Dữ liệu

Dòng đầu tiên chứa số nguyên N, là số đoạn nguyên trong tập hợp.

Dòng thứ i trong số N dòng sau, chứa 2 số nguyên A,B biểu thị cho đoạn i.

Kết quả

Một số duy nhất là kết quả của bài toán.

Giới hạn

1 <= N <= 100000

1 <= A < B <= 1000000

Ví dụ

Dữ liệu
3
1 6
2 5
3 4
 
Kết quả
3

Dữ liệu
6
1 4
1 5
1 6
1 7 
2 5 
3 5
 
Kết quả
5

Chú ý: O(N^2) ăn được 50% số test.

---

• Người up: naruto238
• Nguồn bài: Croatia open contest 07-08