题目描述

给定 n 个整数 a1,a2,...,an ，每个数字都是 0,1,2 中的一个。

可以不断交换这个序列中的任意两个数，从而让这个序列成为单调不递减。

请问最少需要几次交换？

输入格式

第一行输入一个整数 n。 第二行输入 n 个整数，表示 a1,a2,...,an。

输出格式

输出一个整数，表示最少交换次数。

样例输入 1

5
2 0 1 2 0

样例输出 1

1

样例输入 2

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

样例输出 2

6

样例输入 3

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

样例输出 3

6

样例输入 4

3
2 0 1

样例输出 4

2

说明

样例 1 解释

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

数据范围

• 对于 30% 的数据，1 ≤ n ≤ 5000；
• 对于 60% 的数据，1 ≤ n ≤ 1e5；
• 对于 100% 的数据，1 ≤ n ≤ 1e6，0 ≤ Ai ≤ 2。