Олимпиадный тренинг

Задача . B. Оптимальная точка на прямой


Вам задано n точек на прямой своими координатами xi. Найдите точку x такую, что сумма расстояний от неё до остальных точек минимальна.

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

В первой строке находится целое число n (1 ≤ n ≤ 3·105) — количество точек на прямой.

Во второй строке находятся n целых чисел xi ( - 109 ≤ xi ≤ 109) — координаты заданных n точек.

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

Выведите одно целое число x — положение оптимальной точки на прямой. Если существует несколько оптимальных точек выведите положение самой левой из них. Гарантируется, что ответ всегда является целым числом.


Примеры
№Входные данныеВыходные данные
1
4
1 2 3 4
2
Статистика успешных решений по компиляторам
 Кол-во
С++5