Farmer John quer foto do rebanho inteiro de $N$ vacas, $1 \le N \le 100,000$, números $1..N$, para mostrar aos amigos com orgulho.

No dia da foto, correm para formar uma fila arbitrária, posição $i$ com $c_{i}$, $1 \le c_{i} \le N$. Ele tem ideias de ordem.

FJ acredita que Vaca $i$ só à esquerda de $i+1$ para todo $i$, $1 \le i \le N-1$, e $N$ só à esquerda de $1$. Claro, nenhuma à esquerda da primeira, mais à esquerda.

Famintas pelo jantar prometido depois da foto, ele quer rapidez. Não seguem bem ordens: escolhe par vizinho e troca uma vez por minuto. Quanto até ordem aceitável?

Exemplo inicial de cinco vacas:

     Esquerda           Direita
        3  5  4  2  1

Primeiro troca segundo par:

        3  4  5  2 1

Depois o mais à direita:

        3  4  5  1  2

Ordem aceitável em só dois minutos de trocas.

Entrada

• Linha $1$: um inteiro $N$.

• Linhas $2..N+1$: linha $i+1$, número $c_{i}$ da vaca $i$.

Saída

• Linha $1$: menor tempo em minutos para ordem adequada.

Exemplos

Entrada 1

5
3
5
4
2
1

Saída 1

2

Observação

Autor do problema: Travis, 2010