10213 - 三值的排序

排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌序的时候。

在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。

写一个程序计算出，给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数。

Line 1: N (1 <= N <= 1000)

Lines 2-N+1: 每行一个数字，共N行。（1..3）

共一行，一个数字。表示排成升序所需的最少交换次数。

Sorting a Three-Valued Sequence IOI'96 - Day 2 Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.

PROGRAM NAME: sort3 INPUT FORMAT Line 1: N (1 <= N <= 1000), the number of records to be sorted Lines 2-N+1: A single integer from the set {1, 2, 3}

SAMPLE INPUT (file sort3.in) 9 2 2 1 3 3 3 2 3 1

OUTPUT FORMAT A single line containing the number of exchanges required SAMPLE OUTPUT (file sort3.out) 4