Problem description


Konkurs kulinarny
(I)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

Dzisiejsze programy kulinarne często opierają się na gustach kilku jurorów, co może prowadzić do niesprawiedliwych ocen. Jednak nowy program “ChefMaster” zmienia zasady gry! W tej edycji aż miliard jurorów decyduje o przyszłości kucharzy, co daje większą szansę na sprawiedliwą ocenę.

Jasiu, nasz kucharz, bierze udział w programie i przygotował N dań. Jurorzy mają zróżnicowane gusta: dla każdego dania i, posmakuje ono tylko określonej grupie jurorów – od li do ri włącznie. Jedynym warunkiem przejścia do kolejnego etapu jest, aby dla każdych dwóch kolejnych dań i oraz i + 1 istniał juror, który polubi oba dania.

Przed wydaniem Jasiu może jednak dokonywać pewnych zmian w daniach poprzez dwie dostępne operacje:

  • Posolenie dania i – powoduje, że juror o indeksie li przestaje lubić to danie, ale zaczyna smakować ono jurorowi o indeksie (ri+1) (jeśli ri + 1 ≤ 109)

  • Posłodzenie dania i – powoduje, że juror o indeksie ri przestaje lubić to danie, ale zaczyna smakować ono jurorowi o indeksie (li−1) (jeśli li − 1 ≥ 1)

Czasu jest niewiele, a przejście do kolejnego etapu nie jest pewne. Powiedz, ile minimalnie Jasiu musi wykonać operacji posolenia bądź posłodzenia, aby spełnił warunek awansu.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca liczbę dań przygotowanych przez Jasia. W następnych N wierszach znajdują się dwie liczby naturalne li oraz ri oznaczające przedział jurorów, którym początkowo posmakowało danie i.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna znaleźć się jedna liczba całkowita oznaczająca minimalną liczbę operacji, aby Jasiu spełnił warunek przejścia do kolejnego etapu.

Ograniczenia

1 ≤ N ≤ 105, 1 ≤ li ≤ ri ≤ 109

Przykład

Wejście Wyjście
3
1 3
5 7
1 3
2

Wejście Wyjście
3
2 5
4 6
1 4
0
Wejście Wyjście
5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000
1999999680
Wejście Wyjście
5
123456 789012
123 456
12 345678901
123456 789012
1 23
246433
Wejście Wyjście
1
1 400
0