D. Медиана Профессора Р.
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В математической статистике есть такое понятие, как медиана ряда чисел. Медианой ряда чисел называется число, стоящее посередине упорядоченного по возрастанию ряда чисел (в случае, если количество чисел нечётное). Если же количество чисел в ряду чётно, то медианой ряда является полусумма двух стоящих посередине чисел упорядоченного по возрастанию ряда.

Но в Ярославском университете не дремлют и изобрели новое понятие – медиана профессора Р. Определим её. Медианой профессора Р. ряда чисел называют число из этого ряда, ближайшее к полусумме минимального и максимального, причем, если таких чисел несколько, из них выбирается минимальное по значению. Ваша задача – найти медиану Профессора Р. в заданном ряде чисел.

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

В первой строке содержится единственное число n (1 ≤ n ≤ 105) – число элементов.

Во второй строке содержатся n целых чисел ai, разделенных пробелом – элементы ряда чисел (|ai| ≤ 2·109).

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

В единственной строке выведите значение медианы профессора Р. для заданного ряда чисел.

Примеры
Входные данные
5
1 1 1 1 1
Выходные данные
1
Входные данные
3
1 2 3
Выходные данные
2