P1459 [IOI 1996 / USACO2.1] Sorting a Three-Valued Sequence

Sorting is a frequent computational task. Now consider sorting when there are at most three possible values. A practical example is ranking winners of a competition by gold, silver, and bronze medals. In this task, the possible values are only $1,2,3$. We use swaps to arrange the sequence in ascending order. Write a program to compute the minimum number of swaps needed to sort a given sequence consisting only of $1,2,3$ into ascending order.

The first line contains a positive integer $n$, the number of medals. Each of the next $n$ lines contains an integer in $[1,3]$, representing a medal.

Output a single integer, the minimum number of swaps needed to sort the sequence in ascending order.

Constraints For $100\%$ of the testdata, $1 \le n \le 1000$. Translated by ChatGPT 5