Énoncé du problème

Il y a au total $N$ élèves de $1$-ère année au lycée JOI, numérotés de $1$ à $N$.

Un jour, les $N$ élèves de $1$-ère année ont passé un examen. Le score de l'élève $i$ ($1 \le i \le N$) était de $A_i$ points. Ici, les $N$ élèves n'ont pas tous obtenu le même score.

En fonction des résultats de cet examen, la répartition dans les classes pour l'année scolaire suivante est décidée. Plus précisément, un entier $x$ est choisi, et les $N$ élèves sont répartis en $2$ classes de sorte que les élèves ayant un score supérieur ou égal à $x$ points aillent dans la classe préparatoire et que les élèves ayant un score strictement inférieur à $x$ points aillent dans la classe générale.

Ici, on choisit une répartition telle qu'au moins $1$ élève appartienne à chaque classe, et que la différence entre le nombre d'élèves de la classe préparatoire et le nombre d'élèves de la classe générale soit minimale. De plus, s'il existe plusieurs répartitions de ce type, on choisit parmi elles celle qui minimise le nombre d'élèves dans la classe préparatoire.

Étant donné le nombre d'élèves et le score de chacun, écrivez un programme permettant de trouver le score minimal parmi les élèves de la classe préparatoire.

Contraintes

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Il existe $i, j$ ($1 \le i < j \le N$) tels que $A_i \ne A_j$.
• Toutes les valeurs en entrée sont des entiers.

Sous-tâches

1. ($20$ points) $N = 3$.
2. ($20$ points) $A_i$ vaut l'une des valeurs $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ points) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ points) Il n'y a pas de contraintes supplémentaires.

Entrée

L'entrée est donnée sous le format suivant :

N
A_1 A_2 ... A_N

Sortie

Affichez sur $1$ ligne le score minimal parmi les élèves de la classe préparatoire.

Exemples d'entrée et de sortie

Exemple d'entrée $1$

3
1000 500 800

Exemple de sortie $1$

1000

Par exemple, en prenant $x = 900$, l'élève $1$ est affecté à la classe préparatoire et les élèves $2, 3$ sont affectés à la classe générale.

Une autre répartition envisageable consiste à affecter les élèves $1, 3$ à la classe préparatoire et l'élève $2$ à la classe générale. Cela peut être réalisé par exemple en prenant $x = 800$.

Dans chacune de ces $2$ répartitions, la différence entre le nombre d'élèves de la classe préparatoire et celui de la classe générale est de $1$. On choisit donc la première répartition, qui minimise l'effectif de la classe préparatoire. Le score minimal parmi les élèves de la classe préparatoire est alors de $1000$ points.

Cet exemple d'entrée satisfait les contraintes de toutes les sous-tâches.

Exemple d'entrée $2$

6
100 75 41 75 13 89

Exemple de sortie $2$

89

En prenant $x = 89$, les élèves $1, 6$ sont affectés à la classe préparatoire et les élèves $2, 3, 4, 5$ à la classe générale. Le score minimal parmi les élèves de la classe préparatoire est alors de $89$ points.

Cet exemple d'entrée satisfait les contraintes de la sous-tâche $4$.

Exemple d'entrée $3$

6
20 25 12 7 13 16

Exemple de sortie $3$

16

Cet exemple d'entrée satisfait les contraintes des sous-tâches $3, 4$.

Exemple d'entrée $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Exemple de sortie $4$

364353982

Cet exemple d'entrée satisfait les contraintes de la sous-tâche $4$.