Enunciado del problema

En la escuela secundaria JOI hay un total de $N$ estudiantes de $1$-er año, numerados del $1$ al $N$.

Un día, los $N$ estudiantes de $1$-er año realizaron un examen. La puntuación del estudiante $i$ ($1 \le i \le N$) fue de $A_i$ puntos. Aquí, no todos los $N$ estudiantes obtuvieron la misma puntuación.

En función de los resultados de este examen se determina la división de clases para el próximo año escolar. Específicamente, se elige un número entero $x$, y los $N$ estudiantes se dividen en $2$ clases de modo que los estudiantes con una puntuación de $x$ puntos o más pasen a la Clase Avanzada, y los estudiantes con una puntuación menor a $x$ puntos pasen a la Clase Regular.

Aquí, se elige una división tal que al menos $1$ estudiante pertenezca a cada clase y la diferencia entre el número de estudiantes en la Clase Avanzada y el número de estudiantes en la Clase Regular sea mínima. Además, si existen varias divisiones de este tipo, se elige entre ellas aquella que minimice el número de estudiantes en la Clase Avanzada.

Dado el número de estudiantes y la puntuación de cada uno, escribe un programa para hallar la puntuación mínima entre los estudiantes de la Clase Avanzada.

Restricciones

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Existen $i, j$ ($1 \le i < j \le N$) tales que $A_i \ne A_j$.
• Todos los valores de entrada son números enteros.

Subtareas

1. ($20$ puntos) $N = 3$.
2. ($20$ puntos) $A_i$ es uno de $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ puntos) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ puntos) No hay restricciones adicionales.

Entrada

La entrada se proporciona en el siguiente formato:

N
A_1 A_2 ... A_N

Salida

Imprime en $1$ línea la puntuación mínima entre los estudiantes de la Clase Avanzada.

Ejemplos de entrada y salida

Ejemplo de entrada $1$

3
1000 500 800

Ejemplo de salida $1$

1000

Por ejemplo, si $x = 900$, el estudiante $1$ es asignado a la Clase Avanzada y los estudiantes $2, 3$ son asignados a la Clase Regular.

Otra forma posible de dividir a los estudiantes es asignar a los estudiantes $1, 3$ a la Clase Avanzada y al estudiante $2$ a la Clase Regular. Esto se puede lograr, por ejemplo, tomando $x = 800$.

En estas $2$ formas de dividir, la diferencia entre el número de estudiantes de la Clase Avanzada y el número de estudiantes de la Clase Regular es $1$. Por lo tanto, se elige la primera división, que minimiza el número de estudiantes de la Clase Avanzada. En ese caso, la puntuación mínima entre los estudiantes de la Clase Avanzada es de $1000$ puntos.

Este ejemplo de entrada cumple las restricciones de todas las subtareas.

Ejemplo de entrada $2$

6
100 75 41 75 13 89

Ejemplo de salida $2$

89

Si $x = 89$, los estudiantes $1, 6$ son asignados a la Clase Avanzada y los estudiantes $2, 3, 4, 5$ a la Clase Regular. En este caso, la puntuación mínima entre los estudiantes de la Clase Avanzada es de $89$ puntos.

Este ejemplo de entrada cumple las restricciones de la Subtarea $4$.

Ejemplo de entrada $3$

6
20 25 12 7 13 16

Ejemplo de salida $3$

16

Este ejemplo de entrada cumple las restricciones de las Subtareas $3, 4$.

Ejemplo de entrada $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Ejemplo de salida $4$

364353982

Este ejemplo de entrada cumple las restricciones de la Subtarea $4$.