Cho N đoạn thẳng trên trục số, đoạn thứ i có dạng [\(l_i\), \(r_i\)] (bao gồm cả hai đầu mút). Hãy tìm số lượng đoạn phủ nhiều nhất tại một điểm nguyên bất kỳ.

Sử dụng kỹ thuật rời rạc hoá + sweep line (còn gọi là difference array + coordinate compression) để xử lý hiệu quả.

Đầu vào

• Dòng đầu tiên chứa số nguyên N (\(1 \le N \le 10^5\)).
• N dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\), r_i (\(1 \le l_i \le r_i \le 10^9\)).

Đầu ra

Một số nguyên là số lượng đoạn phủ nhiều nhất tại một điểm.

Ví dụ

Input:
4
1 5
2 3
3 8
4 6

Output:
3

Giải thích

Tại x = 4, có 3 đoạn [1,5], [3,8], [4,6] cùng phủ qua.

Ràng buộc & Subtasks