Descripción

Al final de la primera etapa de entrenamiento de la Preselección Nacional de Informática del 2006, se hace una foto de grupo con los ~N~ participantes. Los participantes están numerados del ~1~ al ~N~, por orden de estatura. La estatura del participante ~h~ es ~h~ (~1 \le h \le N~).

Los participantes se colocan en las escaleras para la foto. Hay ~N~ escalones en la escalera. Los escalones están numerados del ~1~ al ~N~, de un lugar más bajo a un lugar más alto.

El escalón ~i + 1~ es más alto que el escalón ~i~ por 2 (~1 \le i \le N - 1~). Como los escalones de la escalera son estrechos, sólo un participante se colocará en cada escalón. Se hará una foto del grupo cuando los participantes estén alineados uno detrás de otros.

Pronto se hará una foto de grupo. Un participante se coloca en cada escalón. Ahora, el participante ~H_i~ se coloca en el escalón ~i~ (~1 \le i \le N~).

Sin embargo, como la diferencia de alturas de los participantes es demasiado grande, si se hace una foto con el orden actual de los participantes, algunos participantes podrían quedar ocultos detrás de otros. Por lo tanto, desea cambiar el orden de los participantes para que al menos la cabeza de cada participante aparezca en la foto. En otras En otras palabras, debe cumplirse la siguiente condición.

• Sea ~a_i~ la altura del participante en el escalón ~i~ (~1 \le i \le N~). Entonces, la desigualdad ~a_i < a_{i+1} + 2~ se satisface para cada ~i~ (~1 \le i \le N - 1~).

Sólo se pueden intercambiar dos participantes consecutivos. Es decir, mediante una operación, se elige un escalón ~i~ (~1 \le i \le N - 1~) arbitrariamente, e intercambias el participante en el escalón ~i~ y el participante en el escalón ~i + 1~.

Quieres minimizar el número de operaciones para que se cumpla la condición anterior.

Tarea

Escribe un programa que, dado el orden de los participantes, calcule el número mínimo de operaciones

Entrada

La entrada se proporciona desde la entrada estándar en el siguiente formato. Todos los valores de entrada son enteros.

~N~

~H_1, ..., H_N~

Salida

Escriba una línea en la salida estándar. La salida debe contener el número mínimo de operaciones.

Restriccciones

• ~3 \le N \le 5 000~.

• ~1 \le H_i \le N~ (~1 \le i \le N~).

• ~H_i~ ≠ ~H_j~ (~1 \le i < j \le N~).

Subtareas

1. (5 puntos) ~N \le 9~.
2. (7 puntos) ~N \le 20~.
3. (32 puntos) ~N \le 200~.
4. (20 puntos) ~N \le 800~.
5. (36 puntos) No hay restricciones adicionales.

Ejemplos de Entrada y Salida

Ejemplo de entrada #1

5
3 5 2 4 1

Ejemplo de salida #1

3

La condición se cumple si se realizan las tres operaciones siguientes.

• En primer lugar, intercambia los participantes en los escalones ~2~ y ~3~. Las alturas de los participantes pasan a ser 3, 2, 5, 4, 1 de un lugar más bajo a un lugar más alto.

• En segundo lugar, se intercambian los participantes en los escalones ~4~ y ~5~. Las alturas de los participantes pasan a ser 3, 2, 5, 1, 4 de un lugar inferior a un lugar superior.

• Por último, intercambia los participantes en los escalones ~3~ y ~4~. Las alturas de los participantes pasan a ser 3, 2, 1, 5, 4 de un lugar más bajo a un lugar más alto. Entonces se cumple la condición.

Como la condición no se cumple si realizas las operaciones menos de tres veces, la salida es ~3~

Ejemplo de entrada #2

5
3 2 1 5 4

Ejemplo de salida #2

0

La condición ya se cumple. No es necesario realizar ninguna operación

Ejemplo de entrada #3

9
6 1 3 4 9 5 7 8 2

Ejemplo de salida #3

9