Aufgabenstellung
Es findet ein Sportturnier statt, an dem $32$ Teams teilnehmen. Jedes Team ist von $1$ bis $32$ nummeriert.
Die Stärke von Team $i$ ($1 \le i \le 32$) beträgt $A_i$, und die Stärken aller Teams sind paarweise verschieden. Wenn $2$ Teams gegeneinander spielen, gewinnt immer das Team mit der größeren Stärke.
Das Turnier wird als K.-o.-Turnier über insgesamt $5$ Runden ausgetragen.
Zu Beginn von Runde $1$ stehen die Teams von links nach rechts in der Reihenfolge der Teams $1, 2, \dots, 32$ in einer Reihe.
In jeder Runde bilden von links nach rechts jeweils $2$ benachbarte Teams ein Paar und spielen gegeneinander. Wenn alle Spiele in dieser Runde beendet sind, rückt jeweils nur der Gewinner jedes Spiels in die nächste Runde vor. Die Gewinner stellen sich in der Reihenfolge, in der ihre Spiele in dieser Runde ausgetragen wurden, von links nach rechts in einer Reihe auf und ziehen in die nächste Runde ein.
Dieser Vorgang wird wiederholt, bis nur noch $1$ Team übrig ist. In Runde $5$ sind noch $2$ Teams übrig und spielen gegeneinander. Dieses Spiel wird Finale genannt; das Team, das das Finale gewinnt, wird Turniersieger, und das Team, das verliert, wird Zweitplatzierter.
Bestimme die Nummer des Teams, das im Finale (dem Spiel in Runde $5$) verliert und Zweitplatzierter wird.
Bedingungen
- $1 \le A_i \le 1\,000$ ($1 \le i \le 32$).
- $A_i \ne A_j$ ($1 \le i < j \le 32$).
- Alle Eingabewerte sind ganze Zahlen.
Eingabe
Die Eingabe erfolgt im folgenden Format:
A_1 A_2 … A_32
Ausgabe
Gib die Nummer des zweitplatzierten Teams aus.
Gib nichts anderes als die Antwort aus. (Gib z. B. auch keinen Text zur Eingabeaufforderung aus.)
Für das Antwortformat kannst du dich an den Übungsaufgaben und ihren Beispiellösungen orientieren.
Beispiel 1
Eingabe
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
Ausgabe
16
Im Spiel der Runde $5$ treten Team $16$ und Team $32$ gegeneinander an. Da die Stärke von Team $16$ gleich $A_{16} = 16$ und die Stärke von Team $32$ gleich $A_{32} = 32$ ist, gewinnt Team $32$ und Team $16$ wird Zweitplatzierter. Daher wird $16$ ausgegeben.
Beispiel 2
Eingabe
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
Ausgabe
25
Im Spiel der Runde $5$ treten Team $11$ und Team $25$ gegeneinander an. Da die Stärke von Team $11$ gleich $A_{11} = 32$ und die Stärke von Team $25$ gleich $A_{25} = 31$ ist, gewinnt Team $11$ und Team $25$ wird Zweitplatzierter. Daher wird $25$ ausgegeben.
Beispiel 3
Eingabe
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
Ausgabe
5
Im Spiel der Runde $5$ treten Team $5$ und Team $22$ gegeneinander an. Da die Stärke von Team $5$ gleich $A_5 = 44$ und die Stärke von Team $22$ gleich $A_{22} = 49$ ist, gewinnt Team $22$ und Team $5$ wird Zweitplatzierter. Daher wird $5$ ausgegeben.
Beispiel 4
Eingabe
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
Ausgabe
5
Im Spiel der Runde $5$ treten Team $5$ und Team $22$ gegeneinander an. Da die Stärke von Team $5$ gleich $A_5 = 912$ und die Stärke von Team $22$ gleich $A_{22} = 975$ ist, gewinnt Team $22$ und Team $5$ wird Zweitplatzierter. Daher wird $5$ ausgegeben.