Duck Pond Gaps

Program time limit: 5 second

Program memory limit: 512 MB

A wildlife explorer has marked several stretches of a long riverbank as suitable nesting areas for ducks.

Each nesting area is represented as an interval on the riverbank by its starting and ending positions. Some nesting areas may overlap.

A gap is a continuous region of the riverbank that is not covered by any nesting area.

Determine the size of the largest gap.

If the nesting areas overlap so much that there are no gaps, output $0$.

Input

The first line contains an integer $N$ $(1 \le N \le 2 \times 10^5)$, the number of nesting areas.

The next N lines each contain two integers $L$ and $R$ $(0 \le L \le R \le 10^9)$, representing the start and end positions of a nesting area.

Output

Output a single integer: the size of the largest gap between nesting areas.

Example

Input

4
1 5
3 8
12 15
20 30

Output

5

Explanation

The first two nesting areas overlap and merge into the interval $[1, 8]$.

The merged nesting areas are: $[1, 8], [12, 15], [20, 30]$.

The gaps are: - Between $8$ and $12$, size 4 - Between $15$ and $20$, size 5

The largest gap has size 5.

Submit

The contest ended at 8:16 p.m. AEST on Thursday 2nd July. All submissions will be unofficial .