Sorting a Three-Valued Sequence

This problem involves sorting a sequence that consists only of three distinct values: 1, 2, and 3. A real-life example is when awarding gold, silver, and bronze medals in a competition.

Your task is to determine the minimum number of swap operations needed to arrange the sequence in ascending order, i.e. all 1's first, then all 2's, and finally all 3's.

Note that the sequence is sorted by swapping any two elements. The problem can be modeled by calculating the number of misplacements in each partition of the sequence.

One standard approach is to:

• Count the number of 1's, 2's, and 3's. Let these counts be c₁, c₂, and c₃ respectively.
• Identify the zones: the first c₁ positions should be 1, the next c₂ positions should be 2, and the remaining positions should be 3.
• Count how many elements are misplaced in each zone. Direct swaps can be performed between pairs of zones where each has an element that belongs in the other, and the remaining cyclic swaps will require two operations.

The formula for the minimal number of swaps can be derived using the counts of misplaced elements and performing optimal pairwise swaps followed by cyclic adjustments if necessary. For example, if n₁₂ is the number of 2's in the first zone and n₂₁ is the number of 1's in the second zone, the number of direct swaps between these zones is min(n₁₂, n₂₁). Similar logic applies for the other pairs.

In summary, given a sequence consisting of the values \(1, 2, 3\), compute the minimum number of swaps needed to sort the sequence in ascending order.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) (where \(1 \le n \le 10^5\)) representing the length of the sequence.
2. The second line contains \(n\) space-separated integers. Each integer is either 1, 2, or 3.

outputFormat

Output a single integer—the minimum number of swap operations required to sort the sequence in ascending order.

sample

5
1 3 2 1 2

2