Game

Interview

Time limit1sMemory limit1024 MB

Summary

Jaime and Cersei take turns subtracting 1 from a suffix of a sorted distinct array, and whoever creates a duplicate or a zero loses. Find the winner.

Level: Medium5 of 10
Topics: Game theory, Math
Solved: No attempts yet

Problem

Jaime and Cersei are playing a game. They have an array of numbers sorted in increasing order. On a turn, a player may subtract 1 from every number in some suffix of the array. A player loses if, after their move, the array contains two equal numbers or one of the numbers becomes zero. Jaime moves first, and Cersei moves second. If both players play optimally, who wins?

Input

The first line contains an integer $n$ ( $1 \le n \le 10^5$ ), the number of elements in the array. The second line contains $n$ distinct integers $a_i$ ( $1 \le a_i \le 10^9$ , $a_{i-1} < a_i$ ), separated by spaces.

Output

Print First if Jaime wins, or Second if Cersei wins.

Examples2

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
Second
```
Example 2
Input
```
1
100
```
Expected output
```
First
```