You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题陈述

给定序列 $a_1, a_2, \ldots, a_n$ ，求从序列中删除元素的最小个数，使得删除后每 $2$ 个连续元素之和为偶数。

输入格式

第一行都包含一个整数 $n$ ( $3 \le n \le 10^6$ )。 第二行包含 $n$ 个整数 $a_1, a_2,\dots,a_n$ （ $1\leq a_i\leq10^9$ ）。( $1\leq a_i\leq10^9$ ) 表示序列元素。

输出格式

打印一个整数表示从序列中删除的最小元素数，以使每个 $2$ 连续元素的和为偶数。

样例1

input

5
2 4 3 6 8

output

1

样例2

input

6
3 5 9 7 1 3

output

0

限制与约定

对于 $30\%$ 的数据，$n \le$ $100$ 。

对于 $60\%$ 的数据，$n \le$ $10^4$

对于 $100\%$ 的数据，$n \le$ $10^6$。

• 时间限制: $1 s$
• 空间限制: $512 MB$