Staircase Nim

Difficulty: 2100 4000 ms 128 MB

math games

Coins sit on stairs 1..N (a_i coins on stair i). A move slides any positive number of coins from stair i down to stair i−1; coins reaching the ground (below stair 1) are gone. The player unable to move loses. Determine the winner.

Input: the first line has N; the second line has the N coin counts.

Output: FIRST or SECOND.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ a_i ≤ 10⁹

Sample Tests

3
1 2 3

FIRST

2
0 5

SECOND

Read the Editorial