Time Limit: 2s
Memory Limit: 256MB
An engineer needs to schedule a machine to run on some given periods $1, \dots, n$ to produce a chemical product $\mathcal{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 $\mathcal{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 $\mathcal{C}$ produced is maximal.
The input consists the following lines:
\begin{itemize}
\item Line 1: contains the positive integer $n$ ($2\leq n\leq 10^6$)
\item Line $i+1$: contains two positive integer $s_i$ and $t_i$ ($1\leq s_i<t_i\leq 10^6$)
\end{itemize}The output consists of only one single integer which is the amount of product $\mathcal{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.
5 8 12 6 11 3 9 2 5 1 4
8
The machine will be runned on two periods [2, 5] and [6, 11] and produce 8 unit of product $\mathcal{C}$.