Умова задачі

У старшій школі 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$.