Description

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.

Input

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}

Output

A single line containing the number of exchanges required

Sample Input


9
2
2
1
3
3
3
2
3
1
Sample Output


4
Source

具体的意思就是，计算给这个数列排序，从小到达，计算最小的交换次数。。

help me

beyondyf 。。。TonyDeng。。。 demonleer 。。。在不啊

help 。。。思路是统计1，2，3个数，然后看1该在的位置，2该。。。。
但听到后面还是不懂。。。。

具体的意思就是，计算给这个数列排序，从小到达，计算最小的交换次数。。

举个小例子嘛。

比如给定一个数列：
S(S) = {1, 3, 2}, 那么如何给他排序呢？ 这个时候我们的目标是把给定的数列排成S(D)= {1, 2, 3},那么我们就依次比较S(S)和S(D)的每个元素：

从第一个开始，发现都是1，不用比较。开始比较第二个，发现一个是3，一个是2，那么我们就把3换到S(S)这个数列中最后一个2的位置。这里的S(S)里只有一个2，所以交换一下就可以了。

如果S(S) = {1,3,2,1,1,2}这样的数列呢？那么我们先要明确，我们的S(D)是多少，那么我们就要统计1的个数，2的个数。统计完毕以后我们就很容易得到S(D) = {1,1,1,2,2,3}。

跟上面一样，我们从S(S)和S(D)的第一个元素开始比较：

1. 第一个元素都是1，比较第二个元素；

2. 第二个元素S(S)里是3，而S(D)里的第二个元素是1，那么我们就把S(S)里的3和S(S)里最后一个1交换位置，得到S(S) = {1,1,2,1,3,2}。

3. 第三个元素S(S)里是2，而S(D)里的第三个元素是1，那么我们就把S(S)里的2和S(S)里最后一个1交换位置，得到S(S) = {1,1,1,2,3,2}。

4. 第四个元素两个集合相同，跳到第5个元素。

5. 第五个元素S(S)里是3，而S(D)里的第五个元素是2，那么我们就把S(S)里的3和S(S)里最后一个2交换位置，得到S(S) = {1,1,1,2,2,3}。

希望妹纸能明白，代码就不写了。

，看明白了，但是为什么总是要最后一个，拿最后一个来交换为什呢是最少次数。。。