Se te da una secuencia $a_0, \dots, a_{2n}$. Inicialmente, todos los números son cero.

Hay $n$ operaciones. La $i$-ésima operación está representada por dos enteros $l_i, r_i$ ($1 \le l_i < r_i \le 2n, 1 \le i \le n$), la cual asigna $i$ a $a_{l_i}, \dots, a_{r_i-1}$. Se garantiza que todos los $2n$ enteros, $l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n$, son distintos.

Debes realizar cada operación exactamente una vez, en un orden arbitrario.

Quieres maximizar el número de $i$ ($0 \le i < 2n$) tales que $a_i \neq a_{i+1}$ después de realizar todas las $n$ operaciones. Imprime el número máximo.

Entrada

La primera línea contiene un entero $n$ ($1 \le n \le 5 \times 10^3$).

La $i$-ésima línea de las siguientes $n$ líneas contiene un par de enteros $l_i, r_i$ ($1 \le l_i < r_i \le 2n$). Se garantiza que todos los $2n$ enteros, $l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n$, son distintos.

Salida

Imprime un único entero que represente la respuesta en una línea.

Ejemplos

Entrada 1

5
2 3
6 7
1 9
5 10
4 8

Salida 1

9