Candy Piles

AtCoder

IDagc002_e

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

2
1 3

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.

Input #2

3
1 2 1

Output #2

First

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

Input #3

3
1 2 3

Output #3

Second

API Response (JSON)

{
  "problem": {
    "name": "Candy Piles",
    "description": {
      "content": "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 go",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc002_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ piles of candies on the table. The piles are numbered $1$ through $N$. At first, pile $i$ contains $a_i$ candies.\nSnuke and Ciel are playing a game. They take alternating turns. Snuke go...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments