Nécessité de la non-décroissance
Étant donné un tableau de
n entiers, votre objectif est de le rendre non décroissant en effectuant l’opération suivante autant de fois que nécessaire (y compris zéro) :Sélectionnez un indice
i (1 ≤ i ≤ n) et remplacez a_i par n’importe quel entier.L’objectif est de minimiser le nombre total d’opérations à effectuer pour rendre le tableau non décroissant.
💡
Formellement, un tableau est dit non décroissant si pour tout et tels que , on a .
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 100 000), représentant la taille du tableau.La deuxième ligne contient
n entiers séparés par des espaces (1 ≤ ≤ ).Sortie
Le programme doit afficher un seul entier — le nombre minimal d’opérations nécessaires pour rendre le tableau non décroissant.
Exemples
Entrée | Sortie |
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