La rivalité séculaire entre Busy Beaver et Busy Revaeb fait rage encore aujourd'hui. Cette fois, ils décident de s'affronter dans un jeu à deux joueurs.
Il existe une séquence de $N$ entiers positifs $a_1, \dots, a_N$. Busy Beaver et Busy Revaeb jouent à un jeu au tour par tour comme suit :
- Busy Beaver choisit deux nombres adjacents dans la séquence, les efface et écrit le plus grand des deux nombres effacés.
- Busy Revaeb fait de même, mais écrit le plus petit des deux nombres effacés.
Busy Beaver commence. Le jeu se termine lorsqu'il ne reste qu'un seul nombre $X$ dans la séquence. Busy Beaver veut maximiser $X$ ; Busy Revaeb veut le minimiser. Trouvez la valeur de $X$ si les deux joueurs jouent de manière optimale.
Entrée
La première ligne contient $N$ ($1 \leq N \leq 2 \cdot 10^5$), le nombre d'éléments dans le tableau.
La deuxième ligne contient $N$ entiers séparés par des espaces $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$).
Sortie
Affichez un seul entier : la valeur du seul élément restant dans le tableau si les deux joueurs jouent de manière optimale.
Scoring
| Sous-tâche | Points | Contraintes |
|---|---|---|
| 1 | 15 | $N \leq 3$ |
| 2 | 25 | $1 \leq a_i \leq 2$ |
| 3 | 60 | Aucune contrainte supplémentaire |
Exemples
| Entrée | Sortie |
|---|---|
32 1 4 |
2 |
41 1 1 2 |
1 |
Note
Explication de l'exemple 1
La dernière valeur ne peut pas être $4$, car si Busy Beaver essaie de garder $4$ en ne le choisissant pas au premier tour, Busy Revaeb peut prendre le $4$ au tour suivant, laissant la dernière valeur à $1$ ou $2$. La dernière valeur ne peut pas non plus être $1$ car Busy Revaeb aurait pu prendre le $1$ au tour $1$, garantissant que la dernière valeur soit supérieure à $1$.
Busy Beaver peut garantir que la dernière valeur soit au moins $2$, et Busy Revaeb peut garantir que la dernière valeur soit au plus $2$. Ainsi, la dernière valeur sera $2$ avec un jeu optimal.
Explication de l'exemple 2
La dernière valeur est soit $1$, soit $2$. Si la stratégie de Busy Revaeb consiste à prendre $2$ dès que possible, alors il peut garantir qu'après son tour (tour $2$), la séquence ne contient que des $1$ — indépendamment de la façon dont Busy Beaver joue au tour $1$. Par conséquent, lorsque les deux jouent de manière optimale, la dernière valeur sera $1$.