In Potatoland, Jiahai the Ultimate Leader of the Potatoes is planning a massive celebration to celebrate the fifth anniversary of Jiahai Potato Farm (JPF), and he wants all the potatoes in his farm to be present for this important occasion.
However, there is a problem. The N potatoes in JPF are incredibly busy, and can each of them is only free during a certain period of time. In particular, potato i is only free from time Ai to time Bi (inclusive). Given all of these values, help Jiahai calculate the length of the longest party he could have where all the potatoes are free (therefore present).
The first line of input will contain one integer, N.
The next N lines of input will contain two integers each, with the ith line containing integers Ai and Bi.
Your output should contain one integer, the length of the longest party Jiahai could have with all the potatoes free.
Your output should be terminated with a newline.
Subtask 1 (17%): 1 ≤ N, Ai, Bi ≤ 1 000
Subtask 2 (25%): 1 ≤ N, Ai, Bi ≤ 1 000 000
Subtask 3 (58%): 1 ≤ N ≤ 1 000 000, 1 ≤ Ai, Bi ≤ 1 000 000 000
Subtask 4 (0%): As per sample testcases
Sample Input 1
Sample Output 1