题目描述

给定 $n$ 个整数排成一圈，两位玩家进行如下的取数规则：

• 第一次取数的玩家可以取任意一个数；
• 第二次取数的玩家只能从上一次取得数的左右两边相邻的两个数中取一个；
• 第三次取数的玩家可以从之前所有取过的任意一个数的左右两边相邻的两个数中取一个；

其中，与第一个数和第 $n$ 个数相邻的只有一个数。

两位玩家轮流取数。在所有的数都被取完之后，取得奇数多的玩家胜利。

请你找出，先手玩家有多少种不同的开局方法，使得自己能够赢得比赛。

输入格式

输入第一行一个整数 $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$ 之间。

说明

题目译自 COCI2006-2007 CONTEST #5 T5 IVANA。