Условие задачи
Проводится спортивный турнир, в котором принимают участие $32$ команды. Каждая команда пронумерована от $1$ до $32$.
Сила команды $i$ ($1 \le i \le 32$) равна $A_i$, причём силы всех команд попарно различны. Когда $2$ команды проводят матч, всегда побеждает команда с большей силой.
Турнир проводится по олимпийской системе (на выбывание) в $5$ раундов.
В начале $1$-го раунда команды выстраиваются в один ряд слева направо в порядке номеров $1, 2, \dots, 32$.
В каждом раунде соседние команды слева направо разбиваются на пары по $2$ команды и проводят матч между собой. Когда все матчи текущего раунда заканчиваются, в следующий раунд проходят только победители каждого матча. Победители выстраиваются в один ряд слева направо в том порядке, в котором проводились их матчи в этом раунде, и переходят в следующий раунд.
Эта процедура повторяется до тех пор, пока не останется $1$ команда. В $5$-м раунде остаются $2$ команды, которые играют между собой. Этот матч называется финалом: команда, победившая в финале, становится чемпионом, а проигравшая команда занимает второе место (становится серебряным призёром).
Найдите номер команды, которая проиграет в финале (матче $5$-го раунда) и займёт второе место.
Ограничения
- $1 \le A_i \le 1\,000$ ($1 \le i \le 32$).
- $A_i \ne A_j$ ($1 \le i < j \le 32$).
- Все входные значения являются целыми числами.
Входные данные
Входные данные подаются в следующем формате:
A_1 A_2 … A_32
Выходные данные
Выведите номер команды, занявшей второе место.
Не выводите ничего, кроме ответа. (Например, не выводите текст с приглашением к вводу.)
Что касается формата ответа, вы можете обратиться к тренировочным задачам и примерам их решений.
Пример 1
Входные данные
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Выходные данные
16
В матче $5$-го раунда встречаются команда $16$ и команда $32$. Поскольку сила команды $16$ равна $A_{16} = 16$, а сила команды $32$ равна $A_{32} = 32$, побеждает команда $32$, а команда $16$ занимает второе место. Следовательно, выводится $16$.
Пример 2
Входные данные
15 17 29 6 7 19 16 26 20 13 32 5 21 4 27 2 22 12 14 28 24 8 30 10 31 1 11 18 25 3 23 9
Выходные данные
25
В матче $5$-го раунда встречаются команда $11$ и команда $25$. Поскольку сила команды $11$ равна $A_{11} = 32$, а сила команды $25$ равна $A_{25} = 31$, побеждает команда $11$, а команда $25$ занимает второе место. Следовательно, выводится $25$.
Пример 3
Входные данные
19 2 5 12 44 40 24 16 3 26 23 21 41 28 9 39 43 22 15 14 7 49 17 46 34 4 32 30 45 27 33 36
Выходные данные
5
В матче $5$-го раунда встречаются команда $5$ и команда $22$. Поскольку сила команды $5$ равна $A_5 = 44$, а сила команды $22$ равна $A_{22} = 49$, побеждает команда $22$, а команда $5$ занимает второе место. Следовательно, выводится $5$.
Пример 4
Входные данные
538 714 395 303 912 315 903 629 588 760 590 344 794 577 541 193 404 325 544 536 435 975 340 511 806 769 44 95 741 519 332 973
Выходные данные
5
В матче $5$-го раунда встречаются команда $5$ и команда $22$. Поскольку сила команды $5$ равна $A_5 = 912$, а сила команды $22$ равна $A_{22} = 975$, побеждает команда $22$, а команда $5$ занимает второе место. Следовательно, выводится $5$.