Sortiere die Zahlen
Angenommen, es liegen
n ganze Zahlen vor, die in aufsteigender Reihenfolge sortiert werden sollen. In jedem Schritt darfst du genau ein Element auswählen und es ganz an den Anfang des Arrays verschieben. Wie viele dieser Operationen sind mindestens nötig, um das Array zu sortieren?Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ).Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ), also die Elemente des Arrays.Ausgabe
Das Programm soll die minimale Anzahl an Operationen ausgeben, die benötigt wird, um das Array zu sortieren.
Beispiele
Eingabe | Ausgabe |
6
11 13 15 12 14 16 | 4 |
10
1 3 2 4 2 4 4 5 9 10 | 3 |
8
3 5 1 5 5 6 7 10 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB