G. Итоговая оценка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп занимается фигурным катанием и участвует в большом соревновании. За его выступлением следили $$$n$$$ судей. Каждый судья поставил оценку за выступление Монокарпа — целое число от $$$1$$$ до $$$10^{9}$$$ (чем выше оценка, тем лучше выступление).

По новым правилам фигурного катания, в соответствии со списком $$$n$$$ оценок судей, итоговая оценка выступления — это ровно одно целое число, получаемое с помощью следующих операций:

  • берется минимальная оценка $$$x$$$ и максимальная оценка $$$y$$$. Обе эти оценки удаляются из списка оценок (если $$$x$$$ встречается в списке несколько раз, удаляется только одно вхождение; то же самое верно для $$$y$$$), а вместо них в список оценок добавляется оценка, равная $$$\frac{x + y}{2}$$$, округленная вниз к ближайшему целому числу.

После применения $$$n - 1$$$ описанных операций в списке оценок останется ровно одна, которая и будет итоговой оценкой выступления.

Перед вами стоит задача определить итоговую оценку выступления Монокарпа.

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

В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество изначальных оценок за выступление Монокарпа.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — изначальные оценки, полученные Монокарпом от судей.

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

Выведите одно целое число — итоговую оценку выступления Монокарпа, которую он получит в соответствии с описанным в условии алгоритмом.

Примеры
Входные данные
5
3 6 1 9 1
Выходные данные
3
Входные данные
8
12 12 40 30 20 24 21 13
Выходные данные
20
Входные данные
3
100 100 100
Выходные данные
100
Примечание

Отсортированный список всех оценок в первом примере равен $$$[1, 1, 3, 6, 9]$$$.

Во время первой операции $$$x = 1$$$, $$$y = 9$$$. Эти оценки удалятся из списка, а добавится оценка $$$\frac{1 + 9}{2} = 5$$$. Поэтому после операции список оценок будет равен $$$[1, 3, 5, 6]$$$.

Во время второй операции $$$x = 1$$$, $$$y = 6$$$. Эти оценки удалятся из списка, а добавится оценка $$$\frac{1 + 6}{2} = 3$$$ (по условию округляем вниз). Поэтому после операции список оценок будет равен $$$[3, 3, 5]$$$.

Во время третьей операции $$$x = 3$$$, $$$y = 5$$$. Эти оценки удалятся из списка, а добавится оценка $$$\frac{3 + 5}{2} = 4$$$. Поэтому после операции список оценок будет равен $$$[3, 4]$$$.

Во время четвертой операции $$$x = 3$$$, $$$y = 4$$$. Эти оценки удалятся из списка, а добавится оценка $$$\frac{3 + 4}{2} = 3$$$ (по условию округляем вниз). Поэтому после операции список оценок будет равен $$$[3]$$$.

Таким образом, в первом итоговая оценка Монокарпа за выступление равна $$$3$$$.