Description

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.

Input Format

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 Format

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

9
2
2
1
3
3
3
2
3
1

4

Hint

Constraints
For $100\%$ of the testdata, $1 \le n \le 1000$.

Translated by ChatGPT 5