1779 - 三元排序
描述

给定一个长度为 N的序列,序列中只包含 1,2,3 三种数字。

现在需要你将序列按升序进行排序,排序必须通过一系列的交换操作来完成。

交换操作是指将两个位置 p 和 q 上的元素进行互换。

请你求出将序列排成升序序列,最少需要进行多少次交换操作。

输入

    第一行读入一个数N,它代表数列的长度。

    以下N行每行一个数。每个数都只可能是1、2、3中的一个。


输出

输出最少的交换次数

样例

输入

9
2
2
1
3
3
3
2
3
1

输出

4
提示

    对于50%的数据,N<=100;

    对于100%的数据,N<=100 000。


题目参数
时间限制 1 秒
内存限制 10 MB
提交次数 3
通过次数 1