排序是一种很频繁的计算任务。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。
写一个程序计算出，计算出的一个包括1、2、3三种值的数字序列，排成升序所需的最少交换次数。
输入第1行为类别的数量N（1≤N≤1000）
输入第2行到第N+1行，每行包括一个数字（1或2或3）。
输出包含一行，为排成升序所需的最少交换次数。
样例输入
9
2
2
1
3
3
3
2
3
1
样例输出
4
import java.util.Scanner;
public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);/** 将题目的数据分为3 个部分* 1.应该为1的部分 A* 2.应该为2的部分 B* 3.应该为3的部分 C* * 例1：2 2 1 3 3 3 2 3 1* 例2：3 2 1 3 3 3 2 2 1* 1.部分A先不管 设x为部分B中3的个数 y为部分C中2的个数* 2.交换max(x,y)次，则部分B中和部分C中的2和3都归位置，* 3.用部分A中不是1的数字 即2或3 分别和部分B和部分C交换* 4.设z为部分A中不是1的个数* 故最少交换次数为 z+max(x,y) */int n = sc.nextInt();int[]num = new int[n+1];int[]len = new int[4];int exchange1 = 0;int exchange2 = 0;int exchange3 = 0;for(int i=1 ;i<=n ;i++){num[i] = sc.nextInt();len[num[i]]++;}for(int i=1; i<=len[1] ;i++){if(num[i] != 1){exchange1++;}}for(int i=len[1]+1; i<=len[1]+len[2] ;i++){if(num[i] == 3){exchange2++;}}for(int i=len[1]+len[2]+1; i<=n ;i++){if(num[i] == 2){exchange3++;}}int sum = exchange1 + Math.max(exchange3, exchange2);System.out.println(sum);}
}