Statement is not available in English language
2. Очередная игра на прямой
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После того, как Миша и Егор целый день играли в одну небезызвестную компьютерную игру, они решили как следует отдохнуть. Для этого они решили сыграть в «Очередную игру на прямой».

Суть этой игры очень проста — есть бесконечная полоска, разделенная на клетки, все клетки которой пронумерованы целыми числами слева направо. Также есть $$$n$$$ подарков, которые лежат в некоторых клетках полоски. Известно, что $$$i$$$-й подарок находится в клетке с номером $$$a_i$$$.

Сначала Миша ставит свою фишку в произвольную клетку. После этого Егор ставит свою фишку в любую клетку, но ему запрещается выбирать ту же клетку, которую выбрал Миша. Затем начинается сама игра. Игроки ходят по очереди, первым ходит Миша. В свой ход игрок может подвинуть свою фишку на одну клетку влево или вправо. Если фишка игрока оказывается в клетке, в которой находится подарок, игрок забирает подарок себе. Цель каждого из игроков — максимизировать количество подарков, которые он заберет. Если игрок изначально ставит свою фишку в клетку с подарком, то он сразу же забирает этот подарок.

Миша и Егор не новички в данной игре, поэтому они знают, что в этой игре существует выигрышная стратегия. Но они ушли спать, поэтому вам придется выяснить, в какую клетку нужно изначально положить фишку Мише, чтобы максимизировать количество подарков, которые он сможет забрать, при условии, что оба игрока играют оптимально и стремятся максимизировать свой выигрыш.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 100\,000$$$) — количество подарков.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — номера клеток, в которых лежат подарки. Гарантируется, что все $$$a_i$$$ попарно различны.

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

Выведите одно целое число $$$p$$$ ($$$-2 \cdot 10^9 \le p \le 2 \cdot 10^9$$$) — номер клетки, в которую нужно изначально положить фишку Мише, чтобы максимизировать количество собранных им подарков.

Если существует несколько оптимальных ответов, выведите любой из них.

Система оценки

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
00Тесты из условияполная
115$$$n \le 100$$$, $$$\lvert a_i \rvert \le 100$$$первая ошибка
220$$$n \le 1\,000$$$, $$$\lvert a_i \rvert \le 1\,000$$$1первая ошибка
320$$$n \le 1\,000$$$1, 2первая ошибка
415$$$0 \le a_i \le 10^6$$$первая ошибка
515$$$1 \le a_i \le n$$$первая ошибка
615нет1 – 5первая ошибка
Примеры
Входные данные
5
1 2 3 4 5
Выходные данные
3
Входные данные
2
1000 -1000
Выходные данные
0
Примечание

Рассмотрим первый пример. Если Миша поставит фишку в третью клетку, то Егор может поставить фишку в четвертую или вторую клетки. Тогда Миша сможет забрать три подарка, а Егор только два.

Во втором примере Миша может встать в любую клетку из отрезка $$$[-1\,000, 1\,000]$$$. Тогда и он, и Егор получат по одному подарку.