CEOI'97 - Nowy Sącz

An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.

Task
Write a program that:

• reads the number of intervals and their descriptions from the text file INT.IN;
• finds the minimal number of elements in a set containing at least two different integers from each interval;
• writes the result to the text file INT.OUT

Input

The first line of the text file INT.IN contains the number of intervals n, 1 Ł n Ł 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.

Output

Your program should write one integer to the first line of the text file INT.OUT; this should be the minimal number of elements in a set containing at least two different integers from each interval.

Example

For the text file INT.IN:

4
3 6
2 4
0 2
4 7

4

Print friendly version