Поначалу у задачи была легенда, связанная с ее названием, но было решено оставить только формальное условие.
Вам заданы \(n\) точек \(a_1, a_2, \dots, a_n\) на оси \(OX\). И теперь вам необходимо найти такую целочисленную точку \(x\) (также на оси \(OX\)), что значение \(f_k(x)\) — минимально возможное.
Функцию \(f_k(x)\) можно описать следующим образом:
- создадим список расстояний \(d_1, d_2, \dots, d_n\) где \(d_i = |a_i - x|\) (т.е. расстояние между \(a_i\) и \(x\));
- отсортируем список \(d\) в неубывающем порядке;
- возьмем в качестве результата значение \(d_{k + 1}\).
Если существует несколько оптимальных ответов, выведите любой.
Выходные данные
Выведите \(T\) целых чисел — соответствующие точки \(x\), которые имеют минимально возможное значение \(f_k(x)\). Если существует несколько ответов — выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2
1 2 5
2 1
1 1000000000
1 0
4
|
3
500000000
4
|