AtCoder Grand Contest 002

E - Candy Piles


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

キャンディの山が N 個あります。 山は 1 から N まで番号が振られています。 最初、i 番目の山には a_i 個のキャンディがあります。

高橋君と青木君がゲームで勝負します。 高橋君と青木君は交互に、次の 2 種類の操作のどちらかを行います。 高橋君が先手です。

  • キャンディが最も多く残っている山をひとつ選び、その山のキャンディをすべて食べる。
  • キャンディが残っているすべての山から、1 個ずつキャンディを食べる。

全体で最後のキャンディを食べた人が負けです。 二人が最適に行動したとき、どちらが勝つかを判定してください。

制約

  • 1≤N≤10^5
  • 1≤a_i≤10^9

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 ... a_N

出力

先手の高橋君が勝つならば First を、後手の青木君が勝つならば Second を出力せよ。


入力例1

2
1 3

出力例1

First

キャンディが最も多いのは 2 番目の山です。 高橋君が 2 番目の山のキャンディをすべて食べると、青木君は最後のキャンディを食べるしかありません。


入力例2

3
1 2 1

出力例2

First

高橋君がすべての山から 1 個ずつキャンディを食べると、青木君は最後のキャンディを食べるしかありません。


入力例3

3
1 2 3

出力例3

Second

Problem Statement

There are N piles of candies on the table. The piles are numbered 1 through N. At first, pile i contains a_i candies.

Snuke and Ciel are playing a game. They take alternating turns. Snuke goes first. In each turn, the current player must perform one of the following two operations:

  1. Choose a pile with the largest number of candies remaining, then eat all candies of that pile.
  2. From each pile with one or more candies remaining, eat one candy.

The player who eats the last candy on the table, loses the game. Determine which player will win if both players play the game optimally.

Constraints

  • 1≤N≤10^5
  • 1≤a_i≤10^9

Input

The input is given from Standard Input in the following format:

N
a_1 a_2  a_N

Output

If Snuke will win, print First. If Ciel will win, print Second.


Sample Input 1

2
1 3

Sample Output 1

First

At the beginning of the game, pile 2 contains the most candies. If Snuke eats all candies of this pile, Ciel has no choice but to eat the last candy.


Sample Input 2

3
1 2 1

Sample Output 2

First

If Snuke eats one candy from each pile, Ciel is again left with the last candy.


Sample Input 3

3
1 2 3

Sample Output 3

Second

Submit提出する