Énoncé du problème
Un tournoi sportif réunissant $32$ équipes va avoir lieu. Chaque équipe est numérotée de $1$ à $32$.
La force de l'équipe $i$ ($1 \le i \le 32$) est $A_i$, et les forces de toutes les équipes sont deux à deux distinctes. Lorsque $2$ équipes s'affrontent lors d'un match, l'équipe ayant la plus grande force gagne toujours.
La compétition se déroule sous la forme d'un tournoi à élimination directe en $5$ tours.
Au début du tour $1$, les équipes sont alignées sur une seule rangée de gauche à droite dans l'ordre des équipes $1, 2, \dots, 32$.
À chaque tour, les équipes adjacentes sont associées par paires de $2$ équipes de gauche à droite et disputent chacune un match. Lorsque tous les matchs de ce tour sont terminés, seul le vainqueur de chaque match passe au tour suivant. Les vainqueurs s'alignent sur une seule rangée de gauche à droite dans l'ordre où leurs matchs ont été joués lors de ce tour, et passent au tour suivant.
Cette opération est répétée jusqu'à ce qu'il ne reste plus qu'une ($1$) équipe. Au tour $5$, il reste $2$ équipes qui disputent un match. Ce match est appelé la finale : l'équipe qui gagne la finale devient championne, et l'équipe qui perd devient vice-championne.
Trouvez le numéro de l'équipe qui perd lors de la finale (le match du tour $5$) et devient vice-championne.
Contraintes
- $1 \le A_i \le 1\,000$ ($1 \le i \le 32$).
- $A_i \ne A_j$ ($1 \le i < j \le 32$).
- Toutes les valeurs d'entrée sont des entiers.
Entrée
L'entrée est donnée sous le format suivant :
A_1 A_2 … A_32
Sortie
Affichez le numéro de l'équipe vice-championne.
N'affichez rien d'autre que la réponse. (N'affichez pas non plus de texte demandant une saisie.)
Pour le format de réponse, vous pouvez consulter les problèmes d'entraînement et leurs exemples de solutions.
Exemple 1
Entrée
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
Sortie
16
Lors du match du tour $5$, l'équipe $16$ et l'équipe $32$ s'affrontent. Comme la force de l'équipe $16$ est $A_{16} = 16$ et celle de l'équipe $32$ est $A_{32} = 32$, l'équipe $32$ l'emporte et l'équipe $16$ devient vice-championne. On affiche donc $16$.
Exemple 2
Entrée
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
Sortie
25
Lors du match du tour $5$, l'équipe $11$ et l'équipe $25$ s'affrontent. Comme la force de l'équipe $11$ est $A_{11} = 32$ et celle de l'équipe $25$ est $A_{25} = 31$, l'équipe $11$ l'emporte et l'équipe $25$ devient vice-championne. On affiche donc $25$.
Exemple 3
Entrée
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
Sortie
5
Lors du match du tour $5$, l'équipe $5$ et l'équipe $22$ s'affrontent. Comme la force de l'équipe $5$ est $A_5 = 44$ et celle de l'équipe $22$ est $A_{22} = 49$, l'équipe $22$ l'emporte et l'équipe $5$ devient vice-championne. On affiche donc $5$.
Exemple 4
Entrée
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
Sortie
5
Lors du match du tour $5$, l'équipe $5$ et l'équipe $22$ s'affrontent. Comme la force de l'équipe $5$ est $A_5 = 912$ et celle de l'équipe $22$ est $A_{22} = 975$, l'équipe $22$ l'emporte et l'équipe $5$ devient vice-championne. On affiche donc $5$.