Aufgabenstellung

An der JOI-Oberschule gibt es insgesamt $N$ Schüler im $1$. Jahrgang, die von $1$ bis $N$ nummeriert sind.

Eines Tages haben die $N$ Schüler des $1$. Jahrgangs eine Prüfung abgelegt. Die Punktzahl von Schüler $i$ ($1 \le i \le N$) betrug $A_i$ Punkte. Hierbei hatten nicht alle $N$ Schüler dieselbe Punktzahl.

Anhand der Ergebnisse dieser Prüfung wird die Klasseneinteilung für das nächste Schuljahr festgelegt. Konkret wird eine ganze Zahl $x$ gewählt, und die $N$ Schüler werden so in $2$ Klassen aufgeteilt, dass Schüler mit mindestens $x$ Punkten in die Fortgeschrittenenklasse und Schüler mit weniger als $x$ Punkten in die Regelklasse kommen.

Dabei wird eine Aufteilung gewählt, bei der jeder Klasse mindestens $1$ Schüler angehört und die Differenz zwischen der Schülerzahl in der Fortgeschrittenenklasse und der Schülerzahl in der Regelklasse minimal ist. Falls mehrere solche Aufteilungen infrage kommen, wird darunter diejenige gewählt, bei der die Schülerzahl in der Fortgeschrittenenklasse minimal ist.

Schreibe ein Programm, das bei gegebener Schülerzahl und den Punktzahlen der einzelnen Schüler die niedrigste Punktzahl unter den Schülern der Fortgeschrittenenklasse bestimmt.

Einschränkungen

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Es gibt $i, j$ ($1 \le i < j \le N$) mit $A_i \ne A_j$.
• Alle Eingabewerte sind ganze Zahlen.

Teilaufgaben

1. ($20$ Punkte) $N = 3$.
2. ($20$ Punkte) $A_i$ ist einer der Werte $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ Punkte) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ Punkte) Es gibt keine zusätzlichen Einschränkungen.

Eingabe

Die Eingabe erfolgt im folgenden Format:

N
A_1 A_2 ... A_N

Ausgabe

Gib die niedrigste Punktzahl unter den Schülern der Fortgeschrittenenklasse in $1$ Zeile aus.

Beispieleingabe und -ausgabe

Beispieleingabe $1$

3
1000 500 800

Beispielausgabe $1$

1000

Wählt man beispielsweise $x = 900$, so wird Schüler $1$ der Fortgeschrittenenklasse und die Schüler $2, 3$ werden der Regelklasse zugeteilt.

Eine weitere denkbare Aufteilung der Schüler besteht darin, die Schüler $1, 3$ der Fortgeschrittenenklasse und Schüler $2$ der Regelklasse zuzuteilen. Dies lässt sich beispielsweise mit $x = 800$ erreichen.

Bei beiden ($2$) Aufteilungen beträgt die Differenz zwischen der Schülerzahl in der Fortgeschrittenenklasse und der Schülerzahl in der Regelklasse $1$. Daher wird die erstgenannte Aufteilung gewählt, bei der die Schülerzahl in der Fortgeschrittenenklasse minimal ist. In diesem Fall beträgt die niedrigste Punktzahl unter den Schülern der Fortgeschrittenenklasse $1000$ Punkte.

Diese Beispieleingabe erfüllt die Einschränkungen aller Teilaufgaben.

Beispieleingabe $2$

6
100 75 41 75 13 89

Beispielausgabe $2$

89

Setzt man $x = 89$, werden die Schüler $1, 6$ der Fortgeschrittenenklasse und die Schüler $2, 3, 4, 5$ der Regelklasse zugeteilt. Dabei beträgt die niedrigste Punktzahl unter den Schülern der Fortgeschrittenenklasse $89$ Punkte.

Diese Beispieleingabe erfüllt die Einschränkungen von Teilaufgabe $4$.

Beispieleingabe $3$

6
20 25 12 7 13 16

Beispielausgabe $3$

16

Diese Beispieleingabe erfüllt die Einschränkungen der Teilaufgaben $3, 4$.

Beispieleingabe $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Beispielausgabe $4$

364353982

Diese Beispieleingabe erfüllt die Einschränkungen von Teilaufgabe $4$.