Ca sĩ nối tiếng Le Roi vừa nhận được các lời mời lưu diễn của n đoàn ca nhạc. Đoàn thứ i mời lưu diễn từ ngày ai đến ngày bi (ai, bi là các số nguyên, ai ≤ bi). Tuy nhiên tại một thời điểm, Le Roi chỉ có thể tham gia hát cho một đoàn duy nhất mà thôi. Với mong muốn đem lời ca tiếng hát của mình đến nhiều khán giả nhất, Le Roi quyết định sẽ chọn tham gia nhiều đoàn nhất có thể. Bạn hãy tính thử xem Le Roi nên chọn tham gia những đoàn nào để số lượng đoàn là nhiều nhất mà không bị trùng nhau về mặt thời gian.

Đầu vào:

Dòng thứ nhất là số nguyên n là số đoàn ca nhạc.

Trong n dòng tiếp theo, dòng thứ i gồm hai số ai, bi cách nhau một khoảng trắng là ngày bắt đầu và ngày kết thúc lưu diễn của đoàn thứ i.

Ràng buộc: 1<=n<=10^5; 1<=ai<=bi<=10^6

Đầu ra: Số nguyên xác định số lượng đoàn nhiều nhất mà Le Roi có thể tham gia.

Input:

6
3 8
9 12
6 10
1 4
2 7
11 14

Output:

3

Cho dãy số A gồm N phần tử là các số nguyên. Hãy tính tích lớn nhất của 2 hoặc 3 phần tử trong dãy.

Đầu vào: Dòng đầu tiên là N; Dòng thứ 2 là N phần tử của mảng A

Ràng buộc: 1<=N<=1000; 0<=abs(A[i])<=10^6

Đầu ra: In ra tích lớn nhất của 2 hoặc 3 phần tử trong mảng

Input:

5
-9 4 3 -3 1

Output:

108

Cho mảng A có n phần tử nguyên dương, hãy in ra số lớn nhất và nhỏ nhất của mọi dãy con liên tiếp có K phần tử của mảng A

Ràng buộc: ~1 \leq N, K \leq 10^6~; ~1 \leq A[i] \leq 10^9~

In ra số lớn nhất và nhỏ nhất của mọi dãy con trên từng dòng

Input:

8 3
8 5 8 6 7 6 5 8

Output:

5 8
5 8
6 8
6 7
5 7
5 8

Giải thích: Tổng bằng 13 và dãy con đó là 6, -5, 12