Trier les nombres
Étant donné
n entiers, vous devez les trier dans l’ordre croissant. À chaque opération, vous êtes autorisé à choisir un élément et à le déplacer tout au début du tableau. Quel est le nombre minimal d’opérations nécessaires pour trier le tableau ?Entrée
La première ligne de l’entrée contient un unique entier
n (1 ≤ n ≤ ).La ligne suivante contient
n entiers séparés par des espaces, (1 ≤ ≤ ), qui représentent les éléments du tableau.Sortie
Le programme doit afficher le nombre minimal d’opérations requis pour trier le tableau.
Exemples
Input | Output |
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