Treść zadania
Odbywa się turniej sportowy, w którym biorą udział $32$ drużyny. Każda drużyna jest ponumerowana od $1$ do $32$.
Siła drużyny $i$ ($1 \le i \le 32$) wynosi $A_i$, a siły wszystkich drużyn są parami różne. Gdy $2$ drużyny rozgrywają mecz, zawsze wygrywa drużyna o większej sile.
Turniej rozgrywany jest systemem pucharowym i składa się łącznie z $5$ rund.
Na początku rundy $1$ drużyny ustawione są w jednym rzędzie od lewej do prawej w kolejności drużyn $1, 2, \dots, 32$.
W każdej rundzie kolejne sąsiadujące ze sobą po $2$ drużyny, licząc od lewej strony, łączą się w pary i rozgrywają ze sobą mecz. Gdy wszystkie mecze w danej rundzie się zakończą, do kolejnej rundy przechodzą wyłącznie zwycięzcy poszczególnych meczów. Zwycięzcy ustawiają się w jednym rzędzie od lewej do prawej w takiej kolejności, w jakiej rozgrywane były ich mecze w tej rundzie, i przechodzą do następnej rundy.
Operację tę powtarza się, aż pozostanie tylko $1$ drużyna. W rundzie $5$ pozostają $2$ drużyny i rozgrywają mecz. Mecz ten nazywamy finałem — drużyna, która wygra finał, zostaje mistrzem, a drużyna, która przegra, zostaje wicemistrzem.
Wyznacz numer drużyny, która przegrywa w finale (meczu w rundzie $5$) i zostaje wicemistrzem.
Ograniczenia
- $1 \le A_i \le 1\,000$ ($1 \le i \le 32$).
- $A_i \ne A_j$ ($1 \le i < j \le 32$).
- Wszystkie wartości wejściowe są liczbami całkowitymi.
Wejście
Wejście podawane jest w następującym formacie:
A_1 A_2 … A_32
Wyjście
Wypisz numer drużyny, która zostanie wicemistrzem.
Nie wypisuj niczego poza odpowiedzią. (Nie wypisuj np. komunikatów proszących o podanie danych.)
Odnośnie formatu odpowiedzi możesz skorzystać z zadań próbnych i ich przykładowych rozwiązań.
Przykład 1
Wejście
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
Wyjście
16
W meczu rundy $5$ grają ze sobą drużyna $16$ i drużyna $32$. Ponieważ siła drużyny $16$ wynosi $A_{16} = 16$, a siła drużyny $32$ wynosi $A_{32} = 32$, wygrywa drużyna $32$, a drużyna $16$ zostaje wicemistrzem. Zatem należy wypisać $16$.
Przykład 2
Wejście
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
Wyjście
25
W meczu rundy $5$ grają ze sobą drużyna $11$ i drużyna $25$. Ponieważ siła drużyny $11$ wynosi $A_{11} = 32$, a siła drużyny $25$ wynosi $A_{25} = 31$, wygrywa drużyna $11$, a drużyna $25$ zostaje wicemistrzem. Zatem należy wypisać $25$.
Przykład 3
Wejście
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
Wyjście
5
W meczu rundy $5$ grają ze sobą drużyna $5$ i drużyna $22$. Ponieważ siła drużyny $5$ wynosi $A_5 = 44$, a siła drużyny $22$ wynosi $A_{22} = 49$, wygrywa drużyna $22$, a drużyna $5$ zostaje wicemistrzem. Zatem należy wypisać $5$.
Przykład 4
Wejście
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
Wyjście
5
W meczu rundy $5$ grają ze sobą drużyna $5$ i drużyna $22$. Ponieważ siła drużyny $5$ wynosi $A_5 = 912$, a siła drużyny $22$ wynosi $A_{22} = 975$, wygrywa drużyna $22$, a drużyna $5$ zostaje wicemistrzem. Zatem należy wypisać $5$.