一家花店有 n 束花束,第 i 束花束由 a 朵花组成。商店经理瓦夏决定用这些花束制作大花束。
Vasya 认为,如果花束由两个或多个初始花束组成,那么它就很大,并且有一个限制:大花束中的花朵总数应该是奇数。每个初始花束最多可以是一个大花束的一部分。如果初始花束成为大花束的一部分,则其所有花朵都包含在大花束中。
确定 Vasya 可以制作的最大可能数量的大花束。
输入
第一行包含一个正整数 n (1 ≤ n ≤ 105) — 初始花束的数量。
第二行包含整数序列 a1, a2, ..., an (1 ≤ ai ≤ 106) — 每个初始花束中的花朵数量。
输出
打印 Vasya 可以制作的大花束的最大数量。
示例
输入 #1
5 2 3 4 2 7
输出 #1
2
输入 #2
6 2 2 6 8 6 12
输出 #2
0
输入 #3
3 11 4 10
输出 #3
1
注意
在第一个示例中,Vasya 可以制作 2 个大花束。例如,第一花束可以包含第一和第五初始花束(则鲜花总数等于9),第二花束可以包含第二和第三初始花束(则鲜花总数等于7)。第四个初始花束在此方案中未使用。
在第二个示例中,不可能用奇数朵花形成单个花束。
在第三个示例中,Vasya 可以制作一大束花。例如,他可以使用所有三个初始花束来制作它。大花束的大小等于 11 + 4 + 10 = 25。