题目描述

给定一个含有 $N$ 个整数，且数组中每个元素的值仅为数字 $1$ 或者 数字 $2$ 的数组。

请编辑数组中的某些位置的数字，将这些位置的数字 $1$ 改成数字 $2$ ，或者将数字 $2$ 改成数字 $1$ ，最终使得数组中所有元素的值满足单调不递减。

请编程计算出，至少要修改多少个位置的数字，才能满足题意。

输入格式

第 $1$ 输入整数 $N$ ，表示数组的长度。

第 $2$ 行，输入 $N$ 个值为 $1$ 或 $2$ 的整数。

输出格式

输出一个整数，表示至少要修改多少个位置的数字，才能满足题意。

样例

输入

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$。