Flip and Slide

Difficulty: 2100 4000 ms 128 MB

math games

Coins 1..N in a row; each is heads (1) or tails (0). A move: choose a heads coin at position i, flip it to tails, and flip EXACTLY ONE coin at a position < i (either direction). The player who cannot move loses. Determine the winner.

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

Output: FIRST or SECOND.

Constraints:

• 1 ≤ N ≤ 10⁵

Sample Tests

4
0 1 0 1

FIRST

3
1 0 0

SECOND

Read the Editorial