AlanashKO adora dinheiro. Na véspera do Ano Novo, recebeu $N$ notas. O valor nominal de cada nota é um inteiro positivo. Enquanto brincava, AlanashKO dispôs todas as notas numa fila e numerou-as da esquerda para a direita, de $1$ a $N$. Depois decidiu ordenar todas as notas por ordem não decrescente. Para isso, AlanashKO executa o seguinte procedimento: primeiro, divide as notas em um ou mais subsegmentos disjuntos, de modo que cada nota pertença a algum subsegmento. Em seguida, os subsegmentos são inseridos, um de cada vez, numa nova fila, pela ordem da esquerda para a direita: primeiro é inserido o subsegmento mais à esquerda (o primeiro subsegmento), depois o seguinte mais à esquerda, e assim por diante. Cada subsegmento é inserido entre quaisquer duas notas ou numa das duas extremidades da nova fila atual. A ordem das notas dentro do subsegmento não é alterada durante a inserção.
AlanashKO quer minimizar o número de subsegmentos que lhe permitam, no fim, ordenar as notas por ordem não decrescente. Ajude-o a encontrar esse valor.
Entrada
A primeira linha contém um único inteiro positivo $N$ ($1 \le N \le 10^6$), o número de notas. A linha seguinte contém $N$ inteiros positivos $a_i$ ($1 \le a_i \le 10^6$), o valor da $i$-ésima nota.
Saída
Imprima numa única linha um único inteiro: o número mínimo de subsegmentos que permitem a AlanashKO ordenar as notas.
Pontuação
Esta tarefa inclui quatro subtarefas:
- $N \le 8$. Vale 9 pontos.
- $N \le 20$. Vale 16 pontos.
- $N \le 300$. Vale 20 pontos.
- $N \le 10^6$. Vale 55 pontos.
Cada subtarefa só será pontuada se a solução passar com sucesso em todas as subtarefas anteriores.
Exemplos
Entrada 1
6 3 6 4 5 1 2
Saída 1
3
Nota
Um subsegmento é uma sequência de elementos consecutivos.
Consideremos o teste de exemplo:
A resposta mínima é a divisão em 3 subsegmentos: |3 6|4 5|1 2| (as barras indicam as fronteiras dos subsegmentos).
Após o primeiro passo: a fila inicial é |4 5|1 2|, e a nova fila é |3 6|.
No segundo passo, o subsegmento |4 5| é inserido entre $3$ e $6$.
Após o segundo passo: a fila inicial é |1 2|, e a nova fila é |3 4 5 6|.
Em seguida, o subsegmento |1 2| é inserido no início da nova fila, obtendo-se |1 2 3 4 5 6|.