A venue's bookings are given as n half-open intervals [start, end). After merging overlapping or touching bookings into solid blocks, report the length of the longest free gap that lies strictly between two consecutive blocks. If there is at most one block (hence no in-between gap), report 0. Free time before the first block or after the last block does not count.
Input format
Line 1: an integer n.
Next n lines: two integers start end (with start < end).
Output format
A single integer: the length of the longest gap between consecutive blocks (0 if none).
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ start < end ≤ 1000000