Verkefnalýsing

Haldið verður íþróttamót þar sem $32$ lið taka þátt. Hvert lið er númerað frá $1$ til $32$.

Styrkur liðs $i$ ($1 \le i \le 32$) er $A_i$, og styrkleikar allra liða eru innbyrðis ólíkir. Þegar $2$ lið keppa í leik vinnur liðið með meiri styrkinn alltaf.

Mótið fer fram sem útsláttarkeppni í alls $5$ umferðum.

Í upphafi $1$. umferðar standa liðin í einni röð frá vinstri til hægri í röðinni lið $1, 2, \dots, 32$.

Í hverri umferð parast hver $2$ samliggjandi lið saman frá vinstri til hægri og spila leik. Þegar öllum leikjum í þeirri umferð er lokið kemst aðeins sigurvegari hvers leiks áfram í næstu umferð. Sigurvegararnir raða sér í eina röð frá vinstri til hægri í þeirri röð sem leikir þeirra fóru fram í þessari umferð og halda áfram í næstu umferð.

Þetta er endurtekið þar til aðeins $1$ lið er eftir. Í $5$. umferð eru $2$ lið eftir og spila leik. Sá leikur kallast úrslitaleikur; liðið sem vinnur úrslitaleikinn verður meistari en liðið sem tapar lendir í öðru sæti.

Finndu númer liðsins sem tapar í úrslitaleiknum (leiknum í $5$. umferð) og lendir í öðru sæti.

Skorður

• $1 \le A_i \le 1\,000$ ($1 \le i \le 32$).
• $A_i \ne A_j$ ($1 \le i < j \le 32$).
• Öll inntaksgildi eru heiltölur.

Inntak

Inntakið er gefið á eftirfarandi sniði:

A_1 A_2 … A_32

Úttak

Prentaðu númer liðsins sem lendir í öðru sæti.

Ekki prenta neitt annað en svarið. (Til dæmis skal ekki prenta texta sem biður um inntak.)

Varðandi snið svarsins má styðjast við æfingadæmin og sýnilausnir þeirra.

Dæmi 1

Inntak

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

Úttak

16

Í leiknum í $5$. umferð mætast lið $16$ og lið $32$. Þar sem styrkur liðs $16$ er $A_{16} = 16$ og styrkur liðs $32$ er $A_{32} = 32$ vinnur lið $32$ og lið $16$ lendir í öðru sæti. Því er prentað $16$.

Dæmi 2

Inntak

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

Úttak

25

Í leiknum í $5$. umferð mætast lið $11$ og lið $25$. Þar sem styrkur liðs $11$ er $A_{11} = 32$ og styrkur liðs $25$ er $A_{25} = 31$ vinnur lið $11$ og lið $25$ lendir í öðru sæti. Því er prentað $25$.

Dæmi 3

Inntak

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

Úttak

5

Í leiknum í $5$. umferð mætast lið $5$ og lið $22$. Þar sem styrkur liðs $5$ er $A_5 = 44$ og styrkur liðs $22$ er $A_{22} = 49$ vinnur lið $22$ og lið $5$ lendir í öðru sæti. Því er prentað $5$.

Dæmi 4

Inntak

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

Úttak

5

Í leiknum í $5$. umferð mætast lið $5$ og lið $22$. Þar sem styrkur liðs $5$ er $A_5 = 912$ og styrkur liðs $22$ er $A_{22} = 975$ vinnur lið $22$ og lið $5$ lendir í öðru sæti. Því er prentað $5$.