#69. 奇偶交替

奇偶交替

题目描述

​ 有 n 只熊,第 i 只熊有一个权值 aia_i 。 ​ 现在梦梦需要将这 n 只熊分组,使得第一组的权值之和为偶数,第二组的权值之和为奇数,第三组的权值之和为偶数,以此类推。 ​ 每只熊需要被分到恰好一组,梦梦想知道最多可以分多少组。 ​

输入格式

​ 一行,给出整数 n 。 ​ 第二行给出整数序列 aia_i 。 ​

输出格式

​ 输出一行,表示答案。 ​

样例

样例输入

7
1 3 5 7 9 11 13                                     

样例输出

样例解释

​ 一组合法解为 1+5,13,7+9+11+31+5, 13, 7+9+11+3

数据范围与提示

​ 对于 30% 的数据, 2n1032 \leq n \leq 10^3 。 ​ 对于 100% 的数据, 2n105,1ai1092 \leq n \leq 10^5,1 \leq a_i \leq 10^9