Prologin
2024
Énoncé¶
Hadès a décidé d'installer un train fantôme aux enfers pour que les âmes perdues aient de quoi s'occuper. L'attraction étant très populaire, les âmes font la queue devant l'attraction. Dans les trains, les âmes sont installées deux par deux. Hadès se rend compte d'un problème dans la file d'attente de l'attraction, les âmes ne sont pas rangées par paires. Par exemple Dalia et Belphegor souhaitent monter ensemble dans le train mais ils ne sont pas arrivés en même temps dans la file, il y a donc d'autres âmes qui les séparent. La file commence à être vraiment dense et les âmes qui attendent à l'entrée de l'attraction gênent la bonne circulation, Hadès vous charge de l'aider.
Triez la file pour que chaque paire d'âmes puisse monter ensemble dans le train. Comme la file est bien remplie, vous ne pouvez la réordonner qu'en échangeant les âmes côte à côte. Pour pouvoir dégager la longue file le plus vite possible, vous cherchez le nombre minimal de permutations que vous devez effectuer.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : $n$, le nombre d'àme présentes dans la file d'attente.
- Sur la ligne suivante, une liste de $n$ entiers séparés par des espaces : queue, la file d'attente.
Les paires sont numérotées de $0$ à $n / 2 - 1$. Chaque âme est représentée par le numéro de la paire à laquelle elle appartient. Donc chaque numéro entre $0$ et $n / 2 - 1$ apparaît deux fois dans la liste.
Sortie¶
Affichez le nombre minimum d'échanges à faire pour trier la file d'attente.
Contraintes¶
- $1 \le n \le 160\,000$