Time Limits: 1000 ms Memory Limits: 65536 KB

Description

Alice想让Bob陪他去看《唐山大地震》,但由于Bob是个很感性的人,怕流泪不想去,但又不好意思以这个作为拒绝的理由,便提出玩一个游戏。
  N个正整数围成一圈,规则如下:
  •两个玩家轮流取数;
  •最开始先手的玩家可以取任意一个数x;
  •从第二步开始当前玩家只能取x(上一玩家刚刚取的数)左右两边相邻的数;
  •直到取完所有的数,游戏结束;
  •取得较多奇数的玩家获胜。
  Bob为了显示大度,让Alice先取,但他忘了自己和Alice都是绝顶聪明之人,现在Alice请你帮他计算第一步有多少种取法使得最终获得胜利。

Input

第一行包含一个整数N(1<=N<=100),表示数的个数。第二行包含N个正整数,每个数都在1到1000之间,任意两个数互不相同。

Output

输出Alice第一步有多少种取法。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
输入1:
3
3 1 5

输入2:
4
1 2 3 4

输入3:
8
4 10 5 2 9 8 1 7

Sample Output

1
2
3
4
5
6
7
8
输出1:
3

输出2:
2

输出3:
5

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define IL inline
using namespace std;
const int N=100;
int n,a[N*2+3];
int f[N*2+3][N*2+3];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
a[i]&=1;
for(int i=1;i<=n;i++)
a[i+n]=a[i];
for(int i=1;i<=n*2;i++)
f[i][i]=a[i];
for(int t=2;t<=n;t++)
for(int i=1;i+t-1<=n*2;i++){
int j=i+t-1;
f[i][j]=max(a[i]-f[i+1][j],a[j]-f[i][j-1]);
}
int ans=0;
for(int i=1;i<=n;i++)
if(a[i]-f[i+1][i+n-1]>0)
ans++;
cout<<ans;
return 0;
}