Problem
Lorsque vous jouez à un nouveau jeu (un hybride de bowling et de billard), N boules sont utilisées, numérotées de 1 à N. Au début du jeu, ces boules doivent être disposées en ligne dans l'ordre numérique. Pendant le jeu, leur ordre peut changer.
Afin d'organiser les balles avant le début du prochain jeu, le dispositif suivant est utilisé. Cet appareil se compose d'une tête qui, se déplaçant sur les balles, peut "aspirer" et "cracher" des ballons. Pour se faire une meilleure idée de cet appareil, imaginez un aspirateur capable d'aspirer des balles, de se déplacer au bon endroit, et là, en soufflant dans le sens opposé, de « recracher » les balles.
Lorsqu'un ballon est aspiré, tous les ballons qui étaient à droite de celui aspiré sont décalés vers la gauche. "Cracher" la balle peut être entre deux balles quelconques (et aussi avant la première balle ou après la dernière), alors la balle qui crache est insérée entre ces balles, et toutes les balles qui sont à droite de celle insérée sont décalées vers la droite .
Plusieurs balles peuvent être aspirées dans l'appareil en même temps, et lors du recrachement de la balle, la dernière balle aspirée est recrachée en premier, puis l'avant-dernière, et ainsi de suite. (c'est-à-dire que l'appareil fonctionne sur le principe d'une pile). Les boules sont recrachées une à la fois, c'est-à-dire vous pouvez recracher une seule boule en laissant le reste à l'intérieur de l'appareil (dans ce cas, vous pouvez continuer à « recracher » les boules au même endroit ou à un autre endroit, ou aspirer de nouvelles boules).
La plus énergivore des opérations décrites est l'opération de succion de la balle, nous voulons donc minimiser le nombre d'opérations de ce type.
Écrivez un programme qui, compte tenu de la disposition initiale des balles, déterminera le nombre minimum d'aspirations nécessaires pour disposer les balles dans l'ordre numérique.
Entrée
Dans le fichier d'entrée, le nombre N est donné en premier — nombre de balles (1≤N≤1000). Ensuite, il y a N nombres qui donnent les numéros des balles dans l'ordre de gauche à droite à leur emplacement actuel (chaque nombre - de 1 à N, et chacun des nombres apparaît exactement une fois dans la séquence).
Sortie
Sortir un seul nombre — le nombre minimum d'opérations d'aspiration de boules qui seront nécessaires pour ranger les boules dans l'ordre de leurs numéros.
Commentaires sur les exemples de tests
1.Vous pouvez aspirer, par exemple, le ballon numéro 2 et le recracher entre le 1er et le 3ème ballon.
2.>Vous pouvez faire quelque chose comme ça. Tout d'abord,
aspirez le ballon numéro 1, puis – balle numéro 2. Ensuite, nous passons au début et recrachons la balle avant la 4ème balle (ce sera la balle numéro 2). Ensuite, aspirez le ballon numéro 3 et recrachez-le entre les ballons 2 et 4. Passez ensuite au début et recrachez-y le ballon numéro 1. Cependant, ce n'est pas le seul ordre possible des ballons dans cet exemple.
| Entrée |
Sortie |
3
2 1 3
1 |
4
4 3 2 1
3 |
Olympiade par équipe, Olympiade par équipe de Moscou, 9e à 11e année, 2007, Ligue A, problème F