You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

有 $n$ 个同学，每个同学都有一个号码牌，第 $i$ 个同学的号码牌上写有一个数字 $a_i$。如果两个同学 $i$ 和 $j$ 的号码牌数字满足 $a_i + a_j$ 为偶数，则他们可以组成一对最佳搭档。

现在需要为这些同学安排搭档（有的同学可以没有搭档），使得最终的最佳搭档对数尽可能多。请计算最多可以组成多少对最佳搭档。

格式

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$。

输出格式

输出一个整数，表示组成最多最佳搭档的数量。

样例

样例输入 #1

5
1 2 3 4 5

样例输出 #1

2

样例解释 #1

可以让第 $1$ 个人和第 $3$ 个人组成最佳搭档。

可以让第 $2$ 个人和第 $4$ 个人组成最佳搭档。

故有 $2$ 对最佳搭档。

数据规模

对于 $100\%$ 的数据，$1\leq n\leq 1000$ ，$1\leq a_i \leq 10^9$。