Problem description

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 l_i do r_i 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 l_i przestaje lubić to danie, ale zaczyna smakować ono jurorowi o indeksie (r_i+1) (jeśli r_i + 1 ≤ 10⁹)

• Posłodzenie dania i – powoduje, że juror o indeksie r_i przestaje lubić to danie, ale zaczyna smakować ono jurorowi o indeksie (l_i−1) (jeśli l_i − 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 l_i oraz r_i 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 ≤ 10⁵, 1 ≤ l_i ≤ r_i ≤ 10⁹

Przykład

3
1 3
5 7
1 3

2

3
2 5
4 6
1 4

0

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

1999999680

5
123456 789012
123 456
12 345678901
123456 789012
1 23

246433

1
1 400

0