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

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

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

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

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

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

【样例 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。