题目描述

给定一个长度为 $N$ 的数组，数组中的每个元素都是 $1$ 或 $2$。

你可以将任意位置的 $1$ 改为 $2$，也可以将 $2$ 改为 $1$。请计算至少修改多少个位置，才能使数组单调不递减。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数，表示给定的数组。

输出格式

输出一个整数，表示最少修改次数。

样例

8
2 1 1 1 2 2 1 2

2

5
2 2 1 2 2

1

15
1 2 1 1 2 1 2 2 2 2 2 2 2 2 1

3

数据范围与提示

• 对于 $60\%$ 的数据，$1 \le N \le 1000$
• 对于 $100\%$ 的数据，$1 \le N \le 10^5$
• 数组中的每个元素均为 $1$ 或 $2$