Existe uma torre de estacionamento circular com $N$ compartimentos dispostos em círculo. Chamam-se compartimento 1, compartimento 2, ..., compartimento $N$, por ordem no sentido horário. Cada um contém um carro. O carro no compartimento $i$ tem o número $a_i$.

A torre tem dois botões. A roda-a um compartimento no sentido horário e B roda-a um compartimento no sentido anti-horário. A figura à esquerda abaixo mostra o exemplo anterior após premir A, e a da direita após premir B.

Queremos retirar todos os carros da torre.

Só se podem retirar carros do único compartimento na posição mais baixa. Inicialmente, o compartimento 1 está nessa posição. Para retirar um carro de outro compartimento, é preciso primeiro premir os botões adequadamente para rodar o seu compartimento até à posição mais baixa.

Além disso, antes de retirar um carro com número $x$, todos os carros com números menores que $x$ devem ser retirados. Ou seja, enquanto restar na torre um carro com número menor que $x$, não se pode retirar um com número $x$.

Escreva um programa que encontre o número mínimo total de vezes que é necessário premir os botões para retirar todos os carros.

Restrições

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

Subtarefas

1. (8 pontos) $a_i=1$ ($1\le i\le N$), isto é, todos os carros têm o número 1.
2. (9 pontos) $a_i\ne a_j$ quando $i\ne j$, isto é, todos os carros têm números distintos.
3. (10 pontos) $N\le10$.
4. (21 pontos) $N\le100$.
5. (31 pontos) $N\le1\,000$.
6. (21 pontos) Sem restrições adicionais.

Entrada

A primeira linha contém um inteiro $N$.

A segunda contém os números dos carros $a_1,\ldots,a_N$ por ordem, separados por espaços.

Saída

Imprima na primeira linha o número mínimo total de vezes que é necessário premir os botões.

Exemplos

Entrada 1

4
1 2 2 1

Saída 1

3

Nota

Pode seguir-se esta ordem: retirar carro → botão A → retirar carro → botão A → retirar carro → botão A → retirar carro.

Entrada 2

5
3 1 4 5 1

Saída 2

7