Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

The title

Now, there is a staircase with NN steps, each of which has several stones, of which the second step has aiai stones (I ≥1i≥1). Two players take turns to operate, each operation can take a number of stones from any step to the next step (can not take). Has been taken on the ground of stones can not be taken, and finally unable to operate as a failure. Ask if the first mover wins if both play the best strategy.

Input format

The first row contains the integer n and the second row contains n integers, where the ith integer represents the number of stones ai on the ith step.

The output format

Prints Yes if the first player must win. Otherwise, output No.

Data range

1 n 1051 n, 105 or less, or less or less or less 1 1091 or less or less ai ai or less 109 or less

Example Input:

3
2 1 3
Copy the code

Example output:

Yes
Copy the code

Train of thought

Odd step is regarded as a classic Nim game. If the xOR value of the value on odd step is 0 when the first hand is played, the first hand will lose; otherwise, the first hand will win. In the case of the first hand, if the odd number of steps are odd or non-zero, according to the classic Nim game, the first hand always has a way to make the odd number of steps odd or equal to zero, so the first hand leaves the odd number of steps odd or equal to zero for the latter hand, and then the latter hand turns: (1) when the successful move even step on stones, stones just move the opponent stones continue to move on to the next step, stones of did not change such an odd number of steps, and so is an odd number of steps for a subsequent party state of exclusive or 0 (2) when to move the stones on the odd steps, for the cause of an odd number of steps to stave or non-zero, according to the classic Nim game, The first hand can always find a way to make the odd number of steps xor 0Copy the code

Ac code

#include <iostream>
using namespace std;
int main(){
    int res = 0;
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        int x;
        cin >> x;
        if(i % 2) res ^= x;
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}
Copy the code