La rivalidad centenaria entre Busy Beaver y Busy Revaeb continúa hasta el día de hoy. Esta vez, han decidido desafiarse en un juego para dos jugadores.
Existe una secuencia de $N$ enteros positivos $a_1, \dots, a_N$. Busy Beaver y Busy Revaeb juegan un juego por turnos de la siguiente manera:
- Busy Beaver elige dos números adyacentes en la secuencia, los borra y escribe el mayor de los dos números borrados.
- Busy Revaeb hace lo mismo, pero escribe el menor de los dos números borrados.
Busy Beaver comienza primero. El juego termina cuando solo queda un número $X$ en la secuencia. Busy Beaver quiere maximizar $X$; Busy Revaeb quiere minimizarlo. Encuentra el valor de $X$ si ambos jugadores juegan de manera óptima.
Entrada
La primera línea contiene $N$ ($1 \leq N \leq 2 \cdot 10^5$), el número de elementos en el arreglo.
La segunda línea contiene $N$ enteros separados por espacios $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$).
Salida
Imprime un único entero: el valor del único elemento que queda en el arreglo si ambos jugadores juegan de manera óptima.
Ejemplos
Entrada 1
3 2 1 4
Salida 1
2
Nota 1
El último valor no puede ser $4$, porque si Busy Beaver intenta mantener el $4$ al no elegirlo en la primera ronda, Busy Revaeb puede tomar el $4$ en la siguiente ronda, dejando como último valor $1$ o $2$. El último valor tampoco puede ser $1$ porque Busy Revaeb podría haber tomado el $1$ en la ronda $1$, asegurando que el último valor sea mayor que $1$.
Busy Beaver puede asegurar que el último valor sea al menos $2$, y Busy Revaeb puede asegurar que el último valor sea como máximo $2$. Por lo tanto, el último valor será $2$ bajo un juego óptimo.
Entrada 2
4 1 1 1 2
Salida 2
1
Nota 2
El último valor es $1$ o $2$. Si la estrategia de Busy Revaeb consiste en tomar el $2$ tan pronto como sea posible, entonces puede garantizar que después de su turno (turno $2$), la secuencia contenga solo $1$s, independientemente de cómo se mueva Busy Beaver en el turno $1$. Por lo tanto, cuando ambos juegan de manera óptima, el último valor será $1$.
Subtareas
- ($15$ puntos) $N \leq 3$.
- ($25$ puntos) $1 \leq a_i \leq 2$.
- ($60$ puntos) Sin restricciones adicionales.