Baralho Embaralhado

Um embaralhamento justo é uma forma de rearranjar $N$ cartas de um baralho disposto horizontalmente da esquerda para a direita. Nesse embaralhamento, as cartas são inicialmente dividas em duas partes contíguas de tamanhos possivelmente diferentes em que uma delas pode ter até mesmo zero cartas! Denotemos por $L$ e $R$ as partes da esquerda e direita, respectivamente. As cartas de $L$ são, então, combinadas com as cartas de $R$, de tal forma que a ordem relativa entre as cartas de cada partição seja mantida.

Você é apresentado à uma disposição final das cartas e deve descobrir qual a quantidade mínima de embaralhamentos justos que devem ser realizados no baralho inicial para que ele chegue a este estado. Inicialmente, as cartas do baralho podem ser vistas como a sequencia $1 2 ... N$. Por exemplo, começando com a sequência $1, 2, 3, 4, 5$ e realizando um embaralhamento justo com $L = 1, 2$ e $R = 3, 4, 5$, podemos obter as seguintes permutações:

• $1, 3, 2, 4, 5$
• $1, 3, 4, 2, 5$
• $3, 4, 5, 1, 2$
• $1, 2, 3, 4, 5$
• etc

Cada uma das permutações acima representa um possı́vel resultado do embaralhamento justo. Note que $1, 3, 2, 5, 4$ não é uma embaralhamento possı́vel pois as ordens relativas das cartas $4$ e $5$ de $R$ não é preservada.

Assuma que o resultado do primeiro embaralhamento é $1, 3, 2, 4, 5$. Se fizermos um segundo embaralhamento justo nele, podemos particionar o baralho em $L = 1, 3, 2, 4$, $R = 5$, e combinar ambas para obter a permutação $1, 3, 2, 5, 4$.

A primeira linha contém um inteiro $N (1 ≤ N ≤ 10^6)$, o número de cartas no baralho. A segunda linha contém uma permutação de números inteiros de $1$ a $N$ descrevendo a disposição final das cartas.

Imprima um único inteiro $K$, que representa o menor número de embaralhamentos justos necessários para obter a permutação dada.