Longest Non‐Decreasing Temperature Period

The Byteotian Institute of Meteorology (BIM) has measured the air temperature for n consecutive days. Due to a printing mishap, the exact temperatures were lost, but for the i-th day the recorded measurement is an interval [l_i, r_i] in which the actual temperature lies. It is known that the measurement error is such that the actual temperature can be arbitrarily chosen within the given interval.

Your task is to help BIM whitewash its negligence by determining the longest contiguous period (subarray) in which it is possible that the actual temperatures were non-decreasing – that is, you can assign for each day a temperature from its interval so that for each day (except the first) the temperature is at least that of the day before.

Input Constraints: 1 ≤ n ≤ 1,000,000, and for each day, l_i and r_i are integers satisfying l_i ≤ r_i.

Mathematical Formulation:

Find the maximum length of an index interval [s, t] such that there exist choices t_s, t_s+1, …, t_t with

[ t_i \in [l_i, r_i] \quad \text{for } i=s,s+1,\ldots,t, ]

and

[ t_s \le t_{s+1} \le \cdots \le t_t. ]

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 1,000,000) representing the number of days. Each of the following n lines contains two integers l_i and r_i (with l_i ≤ r_i), which represent the range of possible temperatures on day i.

Example:

5
3 5
4 6
5 5
4 8
8 9

outputFormat

Output a single integer representing the length of the longest contiguous period in which the temperature could have been non-decreasing.

For the above sample, the output should be:

5

sample

5
3 5
4 6
5 5
4 8
8 9

5