尽管 Ivana 在第二个任务中看到 Zvonko 偷了 Mirko 的微处理器，但因为她喜欢 Zvonko，所以她没有告诉 Mirko。她向 Zvonko 提议一起去看电影，这样她就会“忘记”这件事。

Zvonko 并不太在意女孩子，因为她们会占用他平时用来练习“数学功夫”的宝贵时间。他提议两人玩一个游戏，如果 Ivana 赢了，他们就一起去看电影。Ivana 同意了，她很擅长跳绳，有时还会和她的两个哥哥一起踢足球。

Zvonko 在地板上把 $N$ 个正整数排成一个圈，并解释了规则：

• 第一位玩家选择任意一个数字。
• 第二位玩家选择与第一位玩家所选数字相邻的两个数字之一。
• 接下来的玩家选择与目前已选数字相邻的任意一个数字，依此类推，直到所有数字都被选完。选到更多奇数（不能被 2 整除的数）的玩家获胜。

Zvonko 采取最优策略；他总是寻找能够确保胜利或平局的策略。Zvonko 不知道 Ivana 的水平如何。作为一名真正的绅士，他让 Ivana 先手。

但 Ivana 只关心能否坐在大银幕前挨着 Zvonko，所以她寻求帮助。

请编写一个程序，计算 Ivana 有多少种不同的第一步选择，使得她在此之后有获胜的策略（即在双方均采取最优策略的情况下能够确保获胜）。

输入格式

输入的第一行包含一个整数 $N$（$1 \le N \le 100$），表示圆圈中数字的个数。

第二行包含 $N$ 个由单个空格分隔的整数。所有数字都在 $1$ 到 $1000$ 之间（含 $1$ 和 $1000$）。保证没有重复的数字。

输出格式

在单行中输出满足要求的首步选择数量。

样例

输入样例 1

3
3 1 5

输出样例 1

3

输入样例 2

4
1 2 3 4

输出样例 2

2

输入样例 3

8
4 10 5 2 9 8 1 7

输出样例 3

5

说明

样例 1 说明：无论 Ivana 第一步选择哪个数字，她最终都会得到两个奇数，而 Zvonko 只能得到一个。

样例 2 说明：如果 Ivana 选择其中一个偶数，Zvonko 将选择其中一个奇数并确保平局。如果她选择一个奇数，Zvonko 将不得不选择一个偶数，然后输掉游戏，因为 Ivana 可以拿走另一个奇数。