Робин Гуд и массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды Робин Гуд нашёл массив из $$$n$$$ целых чисел. Он непременно решил уравнять этот массив, то есть сделать все элементы равными. Для этого он может выполнить над массивом несколько (возможно ноль) операций.

За одну операцию Робин Гуд может выбрать три подряд идущих элемента массива и заменить их на медиану этих трёх элементов.

Медианой набора чисел $$$a_1, a_2, \ldots, a_{2m-1}$$$ называется число $$$c_m$$$, где $$$c_1, c_2, \ldots, c_{2m-1}$$$ — набор чисел $$$a_1, a_2, \ldots, a_{2m-1}$$$, отсортированный по неубыванию. Например, медиана набора чисел $$$5, 2, 3$$$ равна $$$3$$$, а медиана набора чисел $$$4, 8, 4$$$ равна $$$4$$$.

Можно показать, что такими операциями всегда можно уравнять массив длины хотя бы $$$3$$$. Например, массив $$$[2, 4, 5, 5, 9]$$$ можно уравнять так: $$$[2, 4, 5, 5, 9] \to [2, 5, 5, 5, 9] \to [5, 5, 5, 5, 9] \to [5, 5, 5, 5, 5]$$$.

Робин Гуд хочет узнать максимальное число, к которому можно приравнять все элементы массива с помощью нескольких применений вышеописанной операции.

Входные данные

В первой строке дано целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива.

Выходные данные

Выведите единственное целое число — ответ на задачу.

Примеры

Входные данные

    51 2 4 4 2

Выходные данные

    4

Входные данные

    64 7 2 1 9 18

Выходные данные

    9

Входные данные

    32 1000000000 2

Выходные данные

    2