题目描述

给定 $n$ 个整数 $a_1,a_2,\dots, a_n$，每个数字都是 $0,1,2$ 中的一个，请将其中的一部分数字两两交换，使得结果是升序的，请问最少需要几次交换？

输入格式

第一行：单个整数表示 $n$ 第二行：$n$ 个整数表示 $a_1,a_2,\dots, a_n$

输出格式

单个整数：表示最少交换次数。

5
2 0 1 2 0

1

样例解释 1

将第一个2与最后一个0交换即可

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 5,000$；
• 对于 $60\%$ 的数据，$1\leq n\leq 100,000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 1,000,000$；
• $0\leq a_i\leq 2$；