Problem
Ao jogar um novo jogo (algum híbrido de boliche e bilhar), N bolas são usadas, numeradas de 1 a N. No início do jogo, essas bolas devem ser dispostas em uma linha em ordem numérica. Durante o jogo, a ordem deles pode mudar.
Para organizar as bolas antes do início do próximo jogo, o seguinte dispositivo é usado. Este dispositivo consiste em uma cabeça que, movendo-se sobre as bolas, pode "sugar" e "cuspir" balões. Para ter uma ideia melhor desse dispositivo, imagine um aspirador de pó que pode sugar bolas, passar para o lugar certo e ali, soprando na direção oposta, “cuspir” as bolas.
Quando um balão é sugado, todos os balões que estavam à direita do sugado são deslocados para a esquerda. "Cuspir" a bola pode estar entre quaisquer duas bolas (e também antes da primeira bola ou depois da última), então a bola cuspida é inserida entre essas bolas, e todas as bolas que estão à direita da inserida são deslocadas para a direita .
Mais de uma bola pode ser sugada para dentro do dispositivo ao mesmo tempo, e ao cuspir a bola, a última bola sugada é cuspida primeiro, depois a penúltima e assim por diante. (ou seja, o dispositivo funciona com base no princípio de uma pilha). As bolas são cuspidas uma de cada vez, ou seja, você pode cuspir apenas uma bola, deixando o restante dentro do aparelho (neste caso, você pode continuar a “cuspir” as bolas no mesmo ou em outro local, ou chupar novas bolas).
A mais intensiva em energia das operações descritas é a operação de chupar a bola, por isso queremos minimizar o número dessas operações.
Escreva um programa que, dada a disposição inicial das bolas, determine o número mínimo de sucções necessárias para dispor as bolas em ordem numérica.
Entrada
No arquivo de entrada, o número N é fornecido primeiro — número de bolas (1≤N≤1000). Depois, há N números que fornecem os números das bolas da esquerda para a direita em sua localização atual (cada número — de 1 a N, e cada um dos números ocorre exatamente uma vez na sequência).
Saída
Entre em um único número — o número mínimo de operações de sucção de bolas que serão necessárias para organizar as bolas na ordem de seus números.
Comentários sobre testes de amostra
1.Você pode chupar, por exemplo, o balão número 2 e cuspi-lo entre o 1º e o 3º balão.
2.>Você pode fazer algo assim. Primeiro,
chupe o balão número 1 e depois – bola número 2. Em seguida, passamos para o início e cuspimos a bola antes da 4ª bola (esta será a bola número 2). Em seguida, sugue o balão número 3 e cuspa entre os balões 2 e 4. Em seguida, vá para o início e ali cuspa o balão número 1. No entanto, esta não é a única ordem possível dos balões neste exemplo.
| Entrada |
Saída |
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
Team Olympiad, Moscow Team Olympiad, séries 9-11, 2007, League A, Problem F