An engineer needs to schedule a machine to run on some given periods 1;..., n to produce a chemical product C. Each period i is represented by a starting time point s\(i\) and terminating time point t\(i\) (s\(i\) < t\(i\)). Due to a technical constraint, the machine must run on exactly two periods that are not overlap (two periods i and j are not overlap if t\(i\) < s\(j\) or t\(j\) < s\(i\)). If the machine is runned on the period i, then the amount of C it will produce is equal to the duration of the period i (which is equal to t\(i\)-s\(i\)). Help the engineer to select two not-overlap periods to run the machine such that the amount of C produced is maximal.

Input

The input consists the following lines:

? Line 1: contains the positive integer n (2 = < n = < 10^6)

? Line i + 1: contains two positive integer s\(i\) and t\(i\) (1 = < s\(i\) < t\(i\) = < 10^6)

Output

The output consists of only one single integer which is the amount of product C the machine will produce in the two selected periods. In case there is no solution (there does not exist two periods that are not overlap), the output contains the value -1.

Example

Input

5

8 12

6 11

3 9

2 5

1 4

Input

8

Explanation

The machine will be runned on two periods [2, 5] and [6, 11] and produce 8 unit of product C.