Status:  Past  Start:  20121013 12:15:00  End:  20121013 16:15:00 
The 2012 Caribbean National Contests of the ACMICPC (CUB)
Problem
2063  A Game with Candies
Created by  Ray Williams Robinson Valiente 
Added by  ymondelo20 (20121012) 
Limits 
Total Time: 20000 MS

Test Time:
4000 MS
Memory: 62 MB  Output: 64 MB  Size:
29 KB

Enabled languages  
Available in 
Description
Shaka and Krysztof are playing an interesting game. They have a sequence of N buildings made of equal candy bricks. Each building has a height which is equal to the number of candies.
Shaka plays first; then Krysztof, then Shaka, then Krysztof and so on. In each move, a player has to find the highest building in the sequence (if there's more than one, he chooses any of them) and reduces its height  that is, eats an arbitrary positive number of candies from that building.
The winner of the game is the one who eats the last candy. Equivalently, the loser of the game is the one who is not able to eat more.
Help Shaka and tell him in how many ways he can play his first move, so that he can certainly win (no matter how Krysztof plays). If Shaka doesn't have a winning strategy at all, the number of ways is zero.
Shaka plays first; then Krysztof, then Shaka, then Krysztof and so on. In each move, a player has to find the highest building in the sequence (if there's more than one, he chooses any of them) and reduces its height  that is, eats an arbitrary positive number of candies from that building.
The winner of the game is the one who eats the last candy. Equivalently, the loser of the game is the one who is not able to eat more.
Help Shaka and tell him in how many ways he can play his first move, so that he can certainly win (no matter how Krysztof plays). If Shaka doesn't have a winning strategy at all, the number of ways is zero.
Shaka and Krysztof are playing an interesting game. They have a sequence of N buildings made of equal candy bricks. Each building has a height which is equal to the number of candies.
Shaka plays first; then Krysztof, then Shaka, then Krysztof and so on. In each move, a player has to find the highest building in the sequence (if there's more than one, he chooses any of them) and reduces its height  that is, eats an arbitrary positive number of candies from that building.
The winner of the game is the one who eats the last candy. Equivalently, the loser of the game is the one who is not able to eat more.
Help Shaka and tell him in how many ways he can play his first move, so that he can certainly win (no matter how Krysztof plays). If Shaka doesn't have a winning strategy at all, the number of ways is zero.
Shaka plays first; then Krysztof, then Shaka, then Krysztof and so on. In each move, a player has to find the highest building in the sequence (if there's more than one, he chooses any of them) and reduces its height  that is, eats an arbitrary positive number of candies from that building.
The winner of the game is the one who eats the last candy. Equivalently, the loser of the game is the one who is not able to eat more.
Help Shaka and tell him in how many ways he can play his first move, so that he can certainly win (no matter how Krysztof plays). If Shaka doesn't have a winning strategy at all, the number of ways is zero.
Shaka and Krysztof are playing an interesting game. They have a sequence of N buildings made of equal candy bricks. Each building has a height which is equal to the number of candies.
Shaka plays first; then Krysztof, then Shaka, then Krysztof and so on. In each move, a player has to find the highest building in the sequence (if there's more than one, he chooses any of them) and reduces its height  that is, eats an arbitrary positive number of candies from that building.
The winner of the game is the one who eats the last candy. Equivalently, the loser of the game is the one who is not able to eat more.
Help Shaka and tell him in how many ways he can play his first move, so that he can certainly win (no matter how Krysztof plays). If Shaka doesn't have a winning strategy at all, the number of ways is zero.
Shaka plays first; then Krysztof, then Shaka, then Krysztof and so on. In each move, a player has to find the highest building in the sequence (if there's more than one, he chooses any of them) and reduces its height  that is, eats an arbitrary positive number of candies from that building.
The winner of the game is the one who eats the last candy. Equivalently, the loser of the game is the one who is not able to eat more.
Help Shaka and tell him in how many ways he can play his first move, so that he can certainly win (no matter how Krysztof plays). If Shaka doesn't have a winning strategy at all, the number of ways is zero.
Input specification
The input will start with a single line saying how many test cases follow (not more than 10). Each test case has the following format:
 First line: an integer N (1 <= N <= 10^5) saying the number of buildings.
 Second line: N space separated integers in the range [0, 10^6] denoting the height of the buildings in the game.
The input will start with a single line saying how many test cases follow (not more than 10). Each test case has the following format:
 First line: an integer N (1 <= N <= 10^5) saying the number of buildings.
 Second line: N space separated integers in the range [0, 10^6] denoting the height of the buildings in the game.
The input will start with a single line saying how many test cases follow (not more than 10). Each test case has the following format:
 First line: an integer N (1 <= N <= 10^5) saying the number of buildings.
 Second line: N space separated integers in the range [0, 10^6] denoting the height of the buildings in the game.
Output specification
Output, for each game, the number of ways for Shaka to make his first move that guarantees him a win.
Output, for each game, the number of ways for Shaka to make his first move that guarantees him a win.
The input will start with a single line saying how many test cases follow (not more than 10). Each test case has the following format:
 First line: an integer N (1 <= N <= 10^5) saying the number of buildings.
 Second line: N space separated integers in the range [0, 10^6] denoting the height of the buildings in the game.
Sample input
4
3
5 2 3
4
5 2 3 3
5
6 6 4 3 2
6
6 6 6 4 3 2
Sample output
1
3
0
18
Hint(s)
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/