题目描述

小 Z 学习了前缀和的概念：

对于数组 $A=[a_1,a_2...a_n]$，其前缀和数组 $B=[a_1,a_1+a_2,a_1+a_2+a_3...a_1+a_2...+a_n]$，即 $b_i=\sum _{i=1}^na_i$。

小 Z 可以对手上的数组 $A$ 随意重新排列，对排列之后 $A$ 的前缀和数组 $B$，最多可以包含多少个奇数元素。

输入格式

第一行，$1$ 个正整数 $n$。

第二行，$n$ 个正整数 $a_i$。

输出格式

一个数字，表示重排 $A$ 之后，$B$ 中最多的奇数个数。

输入输出样例

4
2 3 1 4

3

样例 $\tt \#1$说明

• 原数组为 $[2,3,1,4]$ 可重排为 $[1,2,4,3]$，此时的前缀和数组为 $[1,3,7,10]$，含有 $3$ 个奇数为最大情况。

5
3 4 7 2 3

4

3
8 8 8

0

数据范围

• 对于 $20\%$ 的数据，$n\le 10$
• 对于 $100\%$ 的数据，$1\le n \le 10^5,1\le a_i\le 10^9$