Otrzymujesz ciąg $a_0, \dots, a_{2n}$. Początkowo wszystkie liczby są równe zero.

Dostępnych jest $n$ operacji. $i$-ta operacja jest reprezentowana przez dwie liczby całkowite $l_i, r_i$ ($1 \le l_i < r_i \le 2n$, $1 \le i \le n$), które przypisują wartość $i$ elementom $a_{l_i}, \dots, a_{r_i-1}$. Gwarantuje się, że wszystkie $2n$ liczb $l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n$ jest różnych.

Musisz wykonać każdą operację dokładnie raz, w dowolnej kolejności.

Chcesz zmaksymalizować liczbę takich $i$ ($0 \le i < 2n$), dla których $a_i \neq a_{i+1}$ po wykonaniu wszystkich $n$ operacji. Wypisz tę maksymalną liczbę.

Wejście

Pierwsza linia zawiera liczbę całkowitą $n$ ($1 \le n \le 5 \times 10^3$).

$i$-ta linia z kolejnych $n$ linii zawiera parę liczb całkowitych $l_i, r_i$ ($1 \le l_i < r_i \le 2n$). Gwarantuje się, że wszystkie $2n$ liczb $l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n$ jest różnych.

Wyjście

Wypisz jedną liczbę całkowitą reprezentującą odpowiedź w jednej linii.

Przykład

Wejście 1

5
2 3
6 7
1 9
5 10
4 8

Wyjście 1

9