3108 - Ivana(轮流取数)

通过次数

13

提交次数

34

时间限制 : 1 秒
内存限制 : 128 MB

书接上回

尽管Mirko的妹妹Ivana在第二项任务中看到Zvonko偷了Mirko的微处理器,但她没告诉Mirko,因为她喜欢Zvonko。她“建议”他和她一起去看电影,这样她会“忘记”这件事。Zvonko不太关注女孩们,因为她们会占用他通常花在练习Math-fu上的宝贵时间。他建议他们俩玩个游戏,如果Ivana赢了,他们会去一起看电影。Ivana同意了,她擅长跳绳,有时甚至会和她的两个兄弟踢足球。

Zvonko将N个正整数放在地板上的一个圆圈里,并解释了规则:

  • 第一次取数的玩家可以取任意一个数;
  • 第二次取数的玩家只能从上一次取得数的左右两边相邻的两个数中取一个;
  • 第三次取数的玩家可以从之前所有取过的任意一个数的左右两边相邻的两个数中取一个;
  • 胜者是取出数字中奇数的数量多的那一方

Zvonko总是使用最优的策略;他的目标是胜利或者平局。Zvonko不知道IVANA玩得有多好。Zvonko作为一名真正的骑士(???),骑士精神使得他让IVANA先行动。但IVANA只关心在大屏幕前的Zvonko(铁fw),所以她需要你帮他赢得这场游戏。

编写一个程序,找出IVANA可以做出多少不同的第一步操作,这样她就有机会在之后获胜。

输入

输入第一行一个整数 n ,表示数字的数量。

第二行 n 个数,表示具体的数字。

输出

输出一行一个整数,表示先手玩家赢得比赛的开局种类数。

样例

输入

3
3 1 5

输出

3

输入

4
1 2 3 4

输出

2

输入

8
4 10 5 2 9 8 1 7

输出

5

提示

对于 100\% 的数据,保证 1\le n\le 100,读入的数字都在 1\sim 1000 之间。

来源

COCI