Subtraction Game {2,5}

Difficulty: 1800 5000 ms 128 MB

game-theory grundy

Several piles; a move removes from one pile a number of stones in {2, 5}. A player who cannot move loses. With both playing optimally and the first player moving first, who wins?

Input: the first line has the number of piles K; the second line has the pile sizes.

Output: First or Second.

Constraints:

• 1 ≤ K ≤ 10⁵
• 0 ≤ pile size ≤ 10⁴

Sample Tests

2
3 3

Second

1
0

Second

3
1 2 4

First

Read the Editorial