Nicht absteigende Anforderung
Gegeben ist ein Array aus
n ganzen Zahlen. Um dieses Array nicht absteigend zu machen, dürfen Sie die folgende Operation beliebig oft (auch nullmal) ausführen:Wählen Sie einen beliebigen Index
i (1 ≤ ) und ersetzen Sie durch eine beliebige ganze Zahl.Ziel ist es, die Anzahl der erforderlichen Operationen zu minimieren, um das Array nicht absteigend zu machen.
💡
Formell ist ein Array genau dann nicht absteigend, wenn für alle und mit gilt: .
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 100 000), die Länge des Arrays.Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ).Ausgabe
Das Programm soll eine einzelne ganze Zahl ausgeben — die minimale Anzahl an Operationen, die notwendig ist, damit das Array nicht absteigend wird.
Beispiele
Eingabe | Ausgabe |
7
1 3 2 2 7 4 3 | 3 |
4
1 2 1 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB