Условие задачи

В старшей школе JOI всего $N$ учеников $1$-го года обучения, пронумерованных от $1$ до $N$.

Однажды все $N$ учеников $1$-го года обучения сдавали экзамен. Результат ученика $i$ ($1 \le i \le N$) составил $A_i$ баллов. При этом не все $N$ учеников набрали одинаковое количество баллов.

По результатам этого экзамена определяется распределение по классам на следующий учебный год. А именно, выбирается некоторое целое число $x$, и $N$ учеников делятся на $2$ класса так, что ученики, набравшие $x$ баллов или больше, попадают в профильный класс, а ученики, набравшие менее $x$ баллов, — в обычный класс.

При этом выбирается такое распределение, чтобы в каждом классе был хотя бы $1$ ученик, а разность между количеством учеников в профильном классе и количеством учеников в обычном классе была минимальной. Более того, если таких способов распределения несколько, среди них выбирается тот, при котором количество учеников в профильном классе минимально.

По заданному количеству учеников и баллам каждого ученика напишите программу, которая найдёт минимальный балл среди учеников профильного класса.

Ограничения

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Существуют такие $i, j$ ($1 \le i < j \le N$), что $A_i \ne A_j$.
• Все входные значения являются целыми числами.

Подзадачи

1. ($20$ баллов) $N = 3$.
2. ($20$ баллов) $A_i$ равно одному из чисел $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ баллов) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ баллов) Дополнительных ограничений нет.

Ввод

Входные данные даны в следующем формате:

N
A_1 A_2 ... A_N

Вывод

Выведите в $1$ строке минимальный балл среди учеников профильного класса.

Примеры ввода и вывода

Пример ввода $1$

3
1000 500 800

Пример вывода $1$

1000

Например, если выбрать $x = 900$, то ученик $1$ попадёт в профильный класс, а ученики $2, 3$ — в обычный класс.

Другой возможный способ распределения учеников — отправить учеников $1, 3$ в профильный класс, а ученика $2$ — в обычный класс. Этого можно добиться, например, выбрав $x = 800$.

В обоих этих $2$ способах распределения разность между числом учеников в профильном классе и числом учеников в обычном классе равна $1$. Следовательно, выбирается первый способ, минимизирующий число учеников в профильном классе. При этом минимальный балл среди учеников профильного класса равен $1000$ баллам.

Этот пример удовлетворяет ограничениям всех подзадач.

Пример ввода $2$

6
100 75 41 75 13 89

Пример вывода $2$

89

Если выбрать $x = 89$, то ученики $1, 6$ попадут в профильный класс, а ученики $2, 3, 4, 5$ — в обычный класс. При этом минимальный балл среди учеников профильного класса равен $89$ баллам.

Этот пример удовлетворяет ограничениям подзадачи $4$.

Пример ввода $3$

6
20 25 12 7 13 16

Пример вывода $3$

16

Этот пример удовлетворяет ограничениям подзадач $3, 4$.

Пример ввода $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Пример вывода $4$

364353982

Этот пример удовлетворяет ограничениям подзадачи $4$.