Gom Băng Thông Tần Số Vườn Trường

Mô tả

Trạm phát thanh của trường nội trú trên hải đảo được cấp một dải tần số rất hẹp. Do lịch phát sóng của các câu lạc bộ thay đổi liên tục, sân trường hiện có nhiều đoạn băng thông trống rải rác trên trục tần số, mỗi đoạn là một khoảng liên tục từ tần số L đến tần số R.

Ban kỹ thuật muốn gom các đoạn còn giao nhau lại thành một kênh phát sóng chung để tiết kiệm tài nguyên. Hai đoạn giao nhau nếu có chung một điểm trên trục tần số (kể cả giao tại đúng một điểm đầu/cuối). Nhiệm vụ của bạn là thực hiện việc gom nhóm rồi thông báo độ dài của kênh dài nhất sau khi gom.

Đầu vào

• Dòng đầu chứa số nguyên n — số đoạn băng thông trống.
• n dòng tiếp theo, mỗi dòng chứa hai số nguyên L R mô tả một đoạn [L, R].

Đầu ra

• Một số nguyên duy nhất: độ dài của kênh dài nhất. Độ dài kênh [a, b] là b - a.

Ràng buộc

• 1 ≤ n ≤ 10^5.
• 0 ≤ L ≤ R ≤ 10^9.

Ví dụ

Đầu vào:

4 1 5 3 8 10 12 7 9

Đầu ra:

7

Giải thích:

• [1,5], [3,8], [7,9] giao nhau và gom thành kênh [1, 9] với độ dài 9 - 1 = 8.
• [10, 12] đứng riêng, độ dài 12 - 10 = 2.
• Đáp án là 8.