Polish version    English version  
  Reprezentacja -> Relacje z olimpiad


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
Lista reprezentantów
Osiągnięcia
Relacje z olimpiad
BOI 1999
CEOI 1998
CEOI 1997
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
Ten dokument nie jest dostępny w polskiej wersji językowej.


Problem: INT

Integer Intervals

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
the correct solution is the text file INT.OUT:
4



Wersja do druku