题目描述

到了毕业季了，小 Z 老师正在头疼如何给 $n$ 个纪念品分组来发给各个将要毕业的同学。纪念品编号为 $1,2,\dots,N$，其中编号为 $i$ 的纪念品价值为 $a_i$。

小 Z 老师对如何将这些纪念品分组有一个奇怪的想法：将每个纪念品都放到一个独一无二的分组中去，使得第一组的纪念品的价值之和为偶数，第二组的价值之和为奇数，以此类推，奇偶交替。

小 Z 老师想问，这些纪念品最多可以分成多少组？

输入格式

第一行一个整数 $n$，代表纪念品的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每个纪念品的价值。

输出格式

输出这些纪念品可以分成的最多的组数。数据保证至少存在一种符合要求的分组方案。

样例 #1

样例输入 #1

7
1 3 5 7 9 11 13

样例输出 #1

3

样例 #2

样例输入 #2

7
11 2 17 13 1 15 3

样例输出 #2

5

提示

【样例 1 解释】

分组方案为：$[1,3],[5,7,9],[11,13]$

【样例 2 解释】

分组方案为：$[2],[11],[13,1],[15],[17,3]$

【数据范围】

$2\le n \le 1000,1\le a_i \le 100$。