게임

면접 대비

시간 제한1초메모리 제한1024 MB

요약

두 사람이 번갈아 정렬된 서로 다른 수열의 접미사에서 각 값을 1씩 줄입니다. 같은 값이 생기거나 0이 되게 만든 쪽이 집니다. 선공과 후공 중 승자를 구합니다.

난이도: 보통10점 중 5점
유형: 게임 이론, 수학
정답자: 아직 제출이 없습니다

문제

제이미와 세르세이가 게임을 한다. 두 사람은 오름차순으로 정렬된 배열을 가지고 있다. 한 번의 턴에 플레이어는 배열의 어떤 접미사에 있는 모든 수에서 1을 뺄 수 있다. 턴을 마친 뒤 배열에 같은 수가 두 개 생기거나 수 중 하나가 0이 되면, 그 턴을 둔 플레이어가 진다. 제이미가 먼저 두고, 세르세이가 두 번째로 둔다. 두 사람이 최적으로 플레이하면 누가 이기는가?

입력

첫 줄에 정수 $n$ ( $1 \le n \le 10^5$ )이 주어진다. 배열에 있는 수의 개수다. 둘째 줄에는 서로 다른 정수 $n$ 개 $a_i$ ( $1 \le a_i \le 10^9$ , $a_{i-1} < a_i$ )가 공백으로 구분되어 주어진다.

출력

제이미가 이기면 First, 세르세이가 이기면 Second를 한 줄에 출력한다.

예제2

예제 1
입력
```
5
1 2 3 4 5
```
예상 출력
```
Second
```
예제 2
입력
```
1
100
```
예상 출력
```
First
```