Задача: Бродвей

Знаменитый театральный критик переезжает в Нью-Йорк. Как известно, все театры в Нью-Йорке размещены на Бродвее, поэтому критик тоже, несомненно, поселится на Бродвее, чтобы быть как можно ближе ко всем театрам. Определите номер дома, в котором должен поселиться критик, чтобы суммарное расстояние от его дома до всех театров было бы минимально. Бродвей представляет собой прямую улицу, на котором подряд, на равном расстоянии друг от друга размещены дома, нумерация которых начинается с 1. В одном доме может находиться несколько театров, критик может поселиться в любом доме, даже если в этом доме находится театр.

Входные данные
Первая строка входных данных содержит одно число N (1 ≤ N ≤10⁵)  – количество театров на Бродвее. Далее идет N натуральных чисел, не превосходящих 10⁹  – номера домов, в которых размещены театры.

Выходные данные
Выведите единственное число  – номер дома, в котором должен поселиться критик.

Примеры

Ваш ответ: