標(biāo)簽：博弈論

Leha somehow found an array consisting of?n?integers. Looking at it, he came up with a task. Twoplayers play the game on the array. Players move one by one. The first playercan choose for his move a subsegment of non-zero length with an odd sum ofnumbers and remove it from the array, after that the remaining parts are gluedtogether into one array and the game continues. The second player can choose asubsegment of non-zero length with an even sum and remove it. Loses the one whocan not make a move. Who will win if both play optimally?

Input

First line of input data contains single integer?n?(1?≤?n?≤?10⁶) — length ofthe array.

Next line contains?n?integers?a₁,?a₂,?...,?a_n?(0?≤?a_i?≤?10⁹).

Output

Output answer in single line. "First", if first player wins, and "Second" otherwise (without quotes).

Examples

input

4
1 3 2 3

output

First

input

2
2 2

output

Second

Note

In first sample first player remove whole array in onemove and win.

In second sample first player can't make a move and lose.

?

題意：

給定：長度為N的序列，兩人做游戲，A先手只能取子段和為奇數(shù)的子段，B后手只能取子段和為偶數(shù)的子段，輪到誰不能取就輸，詢問誰最后勝利

分析：這種數(shù)據(jù)范圍，肯定是博弈論辣

如果這個序列整個和為奇數(shù)，那么A先手能夠一次性取完，A勝利

如果序列和為偶數(shù)且整個序列中不存在奇數(shù)，那么A先手無法取，B勝利

如果序列和為偶數(shù)且整個序列中存在奇數(shù)，那么A先手取一個子段和為奇數(shù)的子段，此時序列和為奇數(shù)，B只能夠取一個子段和為偶數(shù)的子段，剩下的奇數(shù)和子段A第二次取完，A勝利

?

Code

#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define mem(x,num) memset(x,num,sizeof x) #define LL unsigned long long using namespace std; LL sum=0,x,n;int main() {int flag=0;scanf("%I64d",&n);rep(i,1,n){scanf("%I64d",&x);x=x%2;sum=(sum+x)%2;if(x==1)flag=1;}if(sum==0&&flag==0)cout<<"Second\n";else cout<<"First\n";return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces841B Godsend的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。