Hay una torre de aparcamiento circular con $N$ compartimentos dispuestos en círculo. Se llaman compartimento 1, compartimento 2, ..., compartimento $N$ en sentido horario. Cada uno contiene un coche. El coche del compartimento $i$ tiene el número $a_i$.

La torre tiene dos botones. A la gira un compartimento en sentido horario y B la gira un compartimento en sentido antihorario. La figura izquierda de abajo muestra el ejemplo anterior tras pulsar A, y la derecha tras pulsar B.

Queremos sacar todos los coches de la torre.

Solo pueden sacarse coches del único compartimento situado en la parte inferior. Inicialmente es el compartimento 1. Para sacar un coche de otro compartimento, primero hay que pulsar los botones adecuadamente para girar su compartimento hasta abajo.

Además, antes de sacar un coche con número $x$, deben haberse sacado todos los coches con números menores que $x$. Es decir, mientras quede en la torre algún coche con número menor que $x$, no puede sacarse uno con número $x$.

Escribe un programa que halle el mínimo número total de pulsaciones necesario para sacar todos los coches.

Restricciones

• $1 \le N \le 100\,000$
• $1 \le a_i \le 1\,000\,000\,000$

Subtareas

1. (8 puntos) $a_i=1$ ($1\le i\le N$), es decir, todos los coches tienen el número 1.
2. (9 puntos) $a_i\ne a_j$ cuando $i\ne j$, es decir, todos los coches tienen números distintos.
3. (10 puntos) $N\le10$.
4. (21 puntos) $N\le100$.
5. (31 puntos) $N\le1\,000$.
6. (21 puntos) Sin restricciones adicionales.

Entrada

La primera línea contiene un entero $N$.

La segunda contiene los números de los coches $a_1,\ldots,a_N$ en orden, separados por espacios.

Salida

Imprime en la primera línea el mínimo número total de pulsaciones.

Ejemplos

Entrada 1

4
1 2 2 1

Salida 1

3

Nota

Puede seguirse este orden: sacar coche → botón A → sacar coche → botón A → sacar coche → botón A → sacar coche.

Entrada 2

5
3 1 4 5 1

Salida 2

7