2063 - A Game with Candies

Created by Ray Williams Robinson Valiente
Added by ymondelo20 (2012-10-12)
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 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 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.

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/