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.