Farmer John quiere foto del rebaño completo de $N$ vacas, $1 \le N \le 100,000$, números $1..N$, para presumir ante amigos.

El día de la foto corren para formar una fila arbitraria, posición $i$ con $c_{i}$, $1 \le c_{i} \le N$. Tiene sus ideas de orden.

FJ cree que Vaca $i$ solo a izquierda de $i+1$ para todo $i$, $1 \le i \le N-1$, y $N$ solo a izquierda de $1$. Claro, ninguna a izquierda de la primera, más a izquierda.

Hambrientas por la cena prometida tras foto, él quiere rapidez. Siguen mal instrucciones: solo elige par adyacente y cambia una vez por minuto. ¿Cuánto tarda en orden aceptable?

Ejemplo inicial de cinco vacas:

     Izquierda           Derecha
        3  5  4  2  1

Primero cambia segundo par:

        3  4  5  2 1

Luego par más a derecha:

        3  4  5  1  2

Orden aceptable con solo dos minutos de cambios.

Entrada

• Línea $1$: un entero $N$.

• Líneas $2..N+1$: línea $i+1$, número $c_{i}$ de vaca $i$.

Salida

• Línea $1$: mínimo tiempo en minutos para orden adecuado.

Ejemplos

Entrada 1

5
3
5
4
2
1

Salida 1

2

Nota

Autor del problema: Travis, 2010