No.761 平均値ゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 46
作問者 : butsurizukibutsurizuki / テスター : matsu7874matsu7874
6 ProblemId : 2552 / 出題時の順位表

メモ

これはAdvent Calendar Contest 2018の9日目用の問題です。

問題

物理好きさんは、以下のようなゲームを考えました。

まず、$N$個の自然数$A_i$を用意します。
プレイヤーは以下の操作のどちらかを行えます。
(i)平均値以上の自然数を全て削除する
(ii)平均値未満の自然数を全て削除する

先攻から交互に操作を行い、先に操作が行えなくなった方が負けです。
なお、1つも数が削除されない操作は行うことができません。

両者が最善を尽くした時、勝つのはどちらか求めてください。

入力

$N$
$A_1$ $A_2$ $...$ $A_N$

・制約
$1 \le N \le 10^5$
$1 \le A_i \le 10^{12}(1 \le i \le N)$
$A_i \le A_{i+1}(1 \le i < N)$

出力

先攻が勝つ場合はFirst、後攻が勝つ場合はSecondを出力し、最後に改行してください。

サンプル

サンプル1
入力
5
1 2 3 5 8
出力
First

先手が先に1,2,3を削除すると後手が5,8のどちらを削除しても先手はもう片方を削除することで勝つことができます。

サンプル2
入力
7
1 3 3 4 575 1333 1640
出力
Second

サンプル3
入力
1
20181209
出力
First

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。