Trier une file – Épreuve régionale 2021

Énoncé¶

Des groupes de gens font la queue, seulement les personnes dans les groupes ne sont pas toutes arrivées en même temps et la file d'attente n'est donc pas triée par groupe.

Pour trier la file d'attente, l'opération de base et d'échanger la place de deux personnes adjacentes.

Étant donnée une position dans la file, on note $k$ le nombre de groupes qui chevauchent cette position, c'est-à-dire le nombre de groupes tels qu'au moins une personne du groupe est avant la position et au moins une personne du groupe est après la position. Comme il y a un système de réservation, le nombre de groupes $k$ qui se chevauchent n'est pas très grand (inférieur à 9).

Trouver le nombre minimum d'échange à faire pour reformer les groupes dans la queue.

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : $n$, la taille de la file d'attente.
• Sur la ligne suivante, un entier : $m$, le nombre de groupes présents dans la file d'attente.
• Sur la ligne suivante, une liste de $n$ entiers séparés par des espaces : file, la file d'attente.

Sortie¶

Affichez le nombre minimum d'échanges à faire pour trier la file d'attente.

Contraintes¶

• $10 \le n \le 10\,000$
• $10 \le m \le 500$