Vườn hoa thành phố Đà Lạt là địa điểm du lịch thu hút nhiều du khách tới tham quan, ngắm hoa và chụp ảnh. Tại đây có n loài hoa được đánh số từ \(1\) tới \(n\), loài hoa thứ \(i\) đẹp nhất trong khoảng thời gian từ \(a_i\) tới \(b_i\) \((a_i \lt b_i)\).
Là một người yêu thích du lịch và đam mê chụp ảnh, Tí không bao giờ bỏ qua những thời điểm có nhiều loài hoa đẹp nhất khi tham quan những địa điểm đó. Lần này, tuy thời gian có hơi gấp gáp, Tí chỉ có thể đến tham quan một lúc rồi đi ngay và chỉ kịp chụp một bức ảnh toàn cảnh vườn hoa. Nhưng may mắn là thời điểm chụp ảnh nằm trong thời điểm mà có nhiều loài hoa nở rộ nhất trong năm.
Yêu cầu:
- Đếm số lượng các loài hoa nở rộ trong bức ảnh Tí chụp.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 10^5)\).
- Dòng thứ \(i\) trong \(n\) dòng tiếp theo mỗi dòng ghi hai số nguyên dương \(a_i\) và \(b_i\) \((1 \le i \le n; 1 \le ai \lt bi \le 10^9)\).
Dữ liệu ra
- Một số nguyên dương duy nhất là đáp án của bài toán.
Input 1
6
1 2
2 3
2 5
5 7
6 7
9 11
Output 1
3
Giải thích:
- Thời điểm chụp hình có nhiều loài hoa nở rộ nhất là \(2\).
- Lúc này có \(3\) loài hoa đang nở rộ là loài hoa số \(1\), số \(2\) và số \(3\).
Ràng buộc:
- 40% số test tương ứng với: \(1 \le n \le 10^3, 1 \le a_i, b_i \le 10^3\)
- 30% số test tương ứng với: \(10^3 \le n \le 10^5, 1 \le a_i, b_i \le 10^6\)
- 30% số test còn lại: Không có thêm ràng buộc gì thêm.
Nhận xét