题目描述

给定 $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

样例解释

将第一个 $2$ 与最后一个 $0$ 交换，序列变为 0 0 1 2 2，满足非递减要求，只需 $1$ 次交换。

15
2 0 2 0 2 0 0 2 0 0 2 0 0 1 1

6

17
2 1 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0

6

3
2 0 1

2

样例解释

初始序列为 2 0 1。一种最优方案为：先交换 $2$ 和 $0$ 得到 0 2 1，再交换 $2$ 和 $1$ 得到 0 1 2，共 $2$ 次交换。

数据范围与提示

• 对于 $30\%$ 的数据：$1 \le n \le 5000$；
• 对于 $60\%$ 的数据：$1 \le n \le 10^5$；
• 对于 $100\%$ 的数据：$1 \le n \le 10^6$，$0 \le a_i \le 2$。