Bé Lợi hôm nay đi tập bắn súng. Trong trường súng có ~n~ tấm bia, tấm bia thứ ~i~ bắt đầu ở vị trí ~a_i~ và kết thúc ở vị trí ~b_i~.
Với uy lực của khẩu AK-47, mỗi viên đạn của khẩu súng có đủ uy lực để xuyên qua tất cả các tấm bia nằm trên quỹ đạo của nó. Khi một viên đạn được bắn ở vị trí ~x~, tất cả các tấm bia có ~a_i \leq x \leq b_i~ sẽ được tính là bị bắn trúng.
Hỏi với hai phát bắn, bé Lợi có thể bắn trúng tối đa bao nhiêu tấm bia? Nếu một tấm bia trúng hai phát đạn, nó cũng chỉ được tính 1 lần.
Input
Dòng đầu nhập số nguyên ~n~ ~(1 \le n \le 10^5)~ là số tấm bia ở trong trường bắn.
Dòng thứ ~i~ trong ~n~ dòng tiếp theo nhập hai số nguyên ~a_i, b_i~ ~(-10^5 \le a_i < b_i \le 10^5)~ mô tả tấm bia thứ ~i~.
Output
- In ra số lượng tấm bia lớn nhất có thể bị Lợi bắn trúng sau hai phát.
Scoring
~30\%~ số test thoả mãn ~n \le 100~.
~30\%~ số test khác có ~n \le 1000~.
~40\%~ số test còn lại không có ràng buộc gì thêm.
Sample Input 1
5
1 2
2 3
3 4
4 5
5 6
Sample Output 1
4
Notes
- Lợi bắn vào hai vị trí ~2~ và ~4~. Khi đó tập các tấm bia bắn trúng (đánh số từ ~1~) sẽ là: ~\{1, 2, 3, 4\}~
Bình luận