Dada una matriz de enteros $A$ de tamaño $N$, la operación de mezcla (shuffle) se define de la siguiente manera:

• Inicialmente, se crea una matriz de enteros vacía $B$.
• Luego, mientras $A$ no esté vacía, se elimina el elemento más a la izquierda o el más a la derecha de $A$, y se añade el valor a la derecha en $B$.
• Si $A$ está vacía, se reemplaza $A$ con $B$ y se detiene.

Si la operación de mezcla se realiza como se muestra en la imagen anterior, el valor de la matriz $A$ cambia de la siguiente manera:

$(34, 19, 5, 36, 4, 25, 12, 9) \to (9, 34, 19, 12, 25, 4, 5, 36)$.

Sea $A_i$ el $i$-ésimo elemento de la matriz $A$. Cuando se cumple la condición "si $1 \le i < j \le N$, entonces $A_i \le A_j$", se dice que la matriz $A$ aumenta monótonamente.

Escriba un programa que, dada una matriz de enteros $A$ de tamaño $N$, calcule el número mínimo de operaciones de mezcla requeridas para hacer que la matriz $A$ aumente monótonamente.

Entrada

La primera línea de la entrada contiene un entero $N$, el número de elementos en la matriz $A$ ($1 \le N \le 3 \cdot 10^5$).

La segunda línea contiene $N$ enteros $A_1, \dots, A_N$: los valores iniciales de los elementos de la matriz $A$ ($1 \le A_i \le 10^9$).

Salida

Imprima el número mínimo de operaciones de mezcla requeridas para hacer que la matriz $A$ aumente monótonamente.

Ejemplos

Entrada 1

3
2 2 5

Salida 1

0

Entrada 2

6
1 5 8 10 3 2

Salida 2

1