Problem
Beim Spielen eines neuen Spiels (eine Mischung aus Bowling und Billard) werden N Kugeln verwendet, die mit Zahlen von 1 bis N nummeriert sind. Zu Beginn des Spiels müssen diese Kugeln in der Reihenfolge ihrer Zahlen in einer Linie angeordnet sein. Während des Spiels kann sich ihre Reihenfolge ändern.
Das folgende Gerät wird verwendet, um die Kugeln vor dem Beginn der nächsten Partie zu ordnen. Dieses Gerät besteht aus einem Kopf, der, wenn er sich über die Kugeln bewegt, «saugen» und « spucken» Kugeln aus. Stellen Sie sich einen Staubsauger vor, der die Kugeln ansaugen, an die richtige Stelle mischen kann, und dort, wenn Sie in die entgegengesetzte Richtung geblasen werden, die Kugeln ausspucken.
Wenn eine Kugel angesaugt wird, werden alle Kugeln, die sich rechts neben der gesaugten befinden, nach links verschoben. Sie können eine Kugel zwischen zwei beliebigen Kugeln ausspucken (sowie vor der ersten Kugel oder nach der letzten Kugel), dann wird die ausspuckte Kugel zwischen diese Kugeln eingefügt, und alle Kugeln, die sich rechts neben der eingelegten Kugel befinden, werden nach rechts verschoben.
Mehr als eine Kugel kann gleichzeitig in das Gerät gesaugt werden, wobei beim Ausspucken der Kugel zuerst die letzte gesaugte Kugel ausgespuckt wird, dann die vorletzte Kugel usw. (d. H. Das Gerät funktioniert nach dem Stapelprinzip). Die Kugeln werden einzeln ausgespuckt, d.h. Sie können nur eine Kugel ausspucken und den Rest im Gerät zurücklassen (dabei können Sie sowohl die Kugeln an derselben oder an anderer Stelle weiter ausspucken als auch neue Kugeln ansaugen).
Die energieintensivste dieser Operationen ist die Operation zum Absaugen des Balls, daher möchte ich die Anzahl solcher Operationen minimieren.
Schreiben Sie ein Programm, das anhand der ursprünglichen Position der Kugeln die minimale Anzahl an Saugvorgängen bestimmt, die benötigt werden, um die Kugeln in der Reihenfolge ihrer Nummern zu platzieren.
Eingabe
In der Eingabedatei wird zuerst die Anzahl N — Anzahl der Kugeln angegeben (1≤N≤1000). Als nächstes kommen N Zahlen, die die Zahlen der Kugeln in der Reihenfolge von links nach rechts an ihrer aktuellen Position angeben (jede Zahl ist von 1 bis N, und jede Zahl wird genau einmal in der Reihenfolge angezeigt).
Ausgabe
Geben Sie in die Ausgabedatei eine Zahl aus, die die minimale Anzahl an Ballsaugvorgängen benötigt, um die Kugeln in der Reihenfolge ihrer Nummer zu platzieren.
Kommentare zu Testbeispielen
1.Sie können zum Beispiel eine Kugel Nummer 2 saugen und sie zwischen der 1. und 3. Kugel ausspucken.
2.>Es ist möglich, zum Beispiel so zu handeln. Zuerst saugen wir
den Ball Nummer 1 ein, dann den Ball Nummer 2. Dann bewegen wir uns zum Anfang und spucken den Ball vor der 4. Kugel aus (dies wird die Kugel Nummer 2 sein). Als nächstes saugen wir den Ball Nummer 3 auf und spucken ihn zwischen den Kugeln 2 und 4 aus. Als nächstes werden wir zum Anfang gehen und dort den Ball Nummer 1 ausspucken. Dies ist jedoch nicht die einzige mögliche Möglichkeit, die Kugeln in diesem Beispiel zu ordnen.
| Eingabe |
Ausgabe |
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
Teamolympiade, Moskauer Teamolympiade, Klassen 9-11, 2007, Liga A, Aufgabe F