Description

给你N个数字，2≤N≤1000 每个数字的值在[1..100]以内 希望将所有的数字分为不相交的若干组 （换句话说，将每头数字分到恰好一组中） 并将这些组排成一行， 使得第一组的数字的品种编号之和为偶数， 第二组的编号之和为奇数，以此类推，奇偶交替。 问可以分成的最大组数是多少？

Format

Input

输入的第一行包含 N。 下一行包含 N 个空格分隔的整数，为 N 头数字的品种编号。

Output

最大组数。可以证明，至少存在一种符合要求的分组方案。

Samples

7
11 2 17 13 1 15 3

5

提示： 在这个样例中，以下是一种分成最大组数五组的方案。将 2 分在第一组，11 分在第二组，13 和 1 分在第三组，15 分在第四组，17 和 3 分在第五组。