E. Игра в уменьшения
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Рассмотрим следующую игру для двух игроков:

  • Изначально на доску выписывается массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$.
  • Игра состоит из раундов. На каждом раунде происходит следующее:
    • Первый игрок выбирает любое $$$i$$$, такое, что $$$a_i \gt 0$$$. Если такого $$$i$$$ не существует, первый игрок проигрывает (второй игрок выигрывает) и игра заканчивается.
    • Второй игрок выбирает любое $$$j \neq i$$$, такое, что $$$a_j \gt 0$$$. Если такого $$$j$$$ не существует, второй игрок проигрывает (первый игрок выигрывает) и игра заканчивается.
    • Вычисляется $$$d = \min(a_i, a_j)$$$. Значения $$$a_i$$$ и $$$a_j$$$ одновременно уменьшаются на $$$d$$$, после чего начинается следующий раунд.

Можно показать, что игра всегда заканчивается после конечного числа раундов.

Выберите, за кого вы хотите сыграть (за первого игрока или за второго) в эту игру, и выиграйте за него.

Входные данные

В первой строке задано целое число $$$n$$$ ($$$1 \le n \le 300$$$) — длина массива $$$a$$$.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 300$$$) — массив $$$a$$$.

Протокол взаимодействия

Взаимодействие начинается после считывания $$$n$$$ и массива $$$a$$$.

Вы должны начать взаимодействие с вывода одной строки «First» или «Second», обозначающей игрока, за которого вы будете играть.

На каждом раунде происходит следующее:

  • Если вы выбрали первого игрока, то вы должны вывести одно целое число $$$i$$$ ($$$1 \le i \le n$$$) в отдельной строке. После этого вы должны считать одно целое число $$$j$$$ ($$$-1 \le j \le n$$$), выведенное в отдельной строке.

    Если $$$j = -1$$$, то это значит, что вы сделали некорректный ход. В таком случае вы должны немедленно завершить вашу программу.

    Если $$$j = 0$$$, то это значит, что второй игрок не может сделать корректный ход, и, соответственно, вы выигрываете игру. В этом случае вы также должны завершить вашу программу.

    Иначе $$$j$$$ равняется индексу, выбранному вторым игроком, и вы должны перейти к следующему раунду.

  • Если вы выбрали второго игрока, то вы должны считать одно целое число $$$i$$$ ($$$-1 \le i \le n$$$), выведенное в отдельной строке.

    Если $$$i = -1$$$, то это значит, что вы сделали некорректный ход на предыдущем раунде. В этом случае вы должны немедленно завершить вашу программу.

    Если $$$i = 0$$$, то это значит, что первый игрок не может сделать корректный ход и вы выигрываете игру. В этом случае вы также должны завершить вашу программу.

    Иначе $$$i$$$ равняется индексу, выбранному первым игроком. В таком случае вы должны вывести одно целое число $$$j$$$ ($$$1 \le j \le n$$$) в отдельной строке и перейти к следующему раунду.

После вывода $$$i$$$ или $$$j$$$ не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Взломы

В этой задаче отключены взломы.

Примеры
Входные данные
4
10 4 6 3


3

1

0
Выходные данные


First
1

2

4
Входные данные
6
4 5 5 11 3 2

2

5

4

6

1

0
Выходные данные


Second 

4

4

3

1

3
Примечание

В первом примере $$$n = 4$$$ и массив $$$a$$$ равен $$$[\, 10, 4, 6, 3 \,]$$$. Ход игры будет следующим:

  • После считывания массива $$$a$$$ программа участника выбирает первого игрока и выводит «First».
  • Первый раунд: первый игрок выбирает $$$i = 1$$$, второй игрок выбирает $$$j = 3$$$. Считается $$$d = \min(a_1, a_3) = \min(10, 6) = 6$$$. Элементы $$$a_1$$$ и $$$a_3$$$ уменьшаются на $$$6$$$. Массив $$$a$$$ становится равен $$$[\, 4, 4, 0, 3 \,]$$$.
  • Второй раунд: первый игрок выбирает $$$i = 2$$$, второй игрок выбирает $$$j = 1$$$. Считается $$$d = \min(a_2, a_1) = \min(4, 4) = 4$$$. Элементы $$$a_2$$$ и $$$a_1$$$ уменюшаются на $$$4$$$. Массив $$$a$$$ становится равен $$$[\, 0, 0, 0, 3 \,]$$$.
  • Третий раунд: первый игрок выбирает $$$i = 4$$$. Не существует $$$j \neq 4$$$, такого, что $$$a_j > 0$$$, поэтому второй игрок не может сделать ход и первый игрок выигрывает. Интерактор выводит $$$j = 0$$$, после считывания которого программа участника завершается.

Во втором примере $$$n = 6$$$ и массив $$$a$$$ равен $$$[\, 4, 5, 5, 11, 3, 2 \,]$$$. Ход игры будет следующим:

  • Программа участника выбирает второго игрока и выводит «Second».
  • Первый раунд: $$$i = 2$$$, $$$j = 4$$$, $$$a = [\, 4, 0, 5, 6, 3, 2 \,]$$$.
  • Второй раунд: $$$i = 5$$$, $$$j = 4$$$, $$$a = [\, 4, 0, 5, 3, 0, 2 \,]$$$.
  • Третий раунд: $$$i = 4$$$, $$$j = 3$$$, $$$a = [\, 4, 0, 2, 0, 0, 2 \,]$$$.
  • Четвертый раунд: $$$i = 6$$$, $$$j = 1$$$, $$$a = [\, 2, 0, 2, 0, 0, 0 \,]$$$.
  • Пятый раунд: $$$i = 1$$$, $$$j = 3$$$, $$$a = [\, 0, 0, 0, 0, 0, 0 \,]$$$.
  • Шестой раунд: первый игрок не может сделать ход и второй игрок выигрывает. Интерактор выводит $$$i = 0$$$, после считывания которого программа участника завершается.

Обратите внимание, что лишние переводы строки в примерах приведены только для удобства и в действительности вам не нужно их выводить. Программа жюри также не будет выводить лишних переводов строки.