Dado um vetor de inteiros $A$ de tamanho $N$, a operação de baralhamento é definida da seguinte forma.

• Inicialmente, cria um vetor de inteiros vazio $B$.
• Depois, enquanto $A$ não estiver vazio, remove o elemento mais à esquerda ou mais à direita de $A$ e acrescenta esse valor à direita em $B$.
• Quando $A$ estiver vazio, substitui $A$ por $B$ e termina.

Se a operação de baralhamento for realizada como na imagem acima, o valor do vetor $A$ é alterado da seguinte forma:

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

Seja $A_i$ o $i$-ésimo elemento do vetor $A$. Quando se verifica a condição «se $1 \le i<j \le N$, então $A_i \le A_j$», diz-se que o vetor $A$ é monotonamente crescente.

Escreva um programa que, dado um vetor de inteiros $A$ de tamanho $N$, calcule o número mínimo de operações de baralhamento necessárias para tornar $A$ monotonamente crescente.

Entrada

A primeira linha da entrada contém um inteiro $N$, o número de elementos do vetor $A$ ($1 \le N \le 3\cdot10^5$).

A segunda linha contém $N$ inteiros $A_1,\ldots,A_N$: os valores iniciais dos elementos do vetor $A$ ($1 \le A_i \le 10^9$).

Saída

Imprima o número mínimo de operações de baralhamento necessárias para tornar o vetor $A$ monotonamente crescente.

Exemplos

Entrada 1

3
2 2 5

Saída 1

0

Entrada 2

6
1 5 8 10 3 2

Saída 2

1