Контрольный результат тренера

В школьной секции по бегу тренер записал времена (в секундах) всех участников на короткой дистанции.

Чтобы поставить «контрольный результат» на следующую тренировку, он хочет выбрать такое время T, что:

• как минимум половина участников бежали не быстрее T (то есть их время ≥ T),
• и как минимум половина участников бежали не медленнее T (то есть их время ≤ T).

Если подходящих значений несколько (это бывает при чётном числе участников), тренер выбирает меньшее из них.

Найдите выбранное время T.

Формат ввода

Первая строка: целое число n — число участников. Вторая строка: n целых чисел a1, a2, ..., an — времена участников.

Формат вывода

Выведите одно целое число — контрольный результат T.

Ограничения

• 1 ≤ n ≤ 20000
• 1 ≤ ai ≤ 1000000

Пример

Ввод:

5
12 7 10 7 9

Вывод:

9

Ключевое наблюдение: условия про «как минимум половина не быстрее T» (времена ≥ T) и «как минимум половина не медленнее T» (времена ≤ T) ровно описывают медиану набора.

Если n нечётное, медиана единственная. Если n чётное, подходят все значения между двумя центральными элементами включительно, а по правилу «взять меньшее» нужно выбрать левый из двух центральных — это называют *нижняя медиана*.

Почему работает сортировка: после упорядочивания легко посчитать, сколько элементов слева (≤) и справа (≥) от выбранного.

План решения:

• Считай n и массив времен.
• Отсортируй массив по возрастанию.
• Возьми элемент с индексом k = (n - 1) // 2 (нумерация с нуля).
• Выведи a[k].

Мини-сниппет с формулой индекса:

• k = (n - 1) // 2

Сложность: сортировка занимает O(n log n) по времени, память O(n).

Частая ошибка: при чётном n брать n//2 (верхнюю медиану). Здесь нужно именно меньшее подходящее, значит индекс (n-1)//2.