Вам дан массив \(a\) из \(n\) целых чисел, где \(n\) нечётно. Вы можете проделать с массивом следующую операцию:
- Выбрать один из элементов массива (например \(a_i\)) и увеличить его на \(1\) (то есть заменить на \(a_i + 1\)).
Вы хотите сделать медиану массива максимально большой, используя не более \(k\) операций.
Медианой нечётного по размеру массива называется средний элемент, если массив отсортировать по неубыванию. Например, медианой массива \([1, 5, 2, 3, 5]\) является \(3\).
Выходные данные
Выведите одно целое число — наибольшую возможную медиану после всех операций.
Примечание
В первом примере можно два раза увеличить второй элемент. Тогда массив будет равен \([1, 5, 5]\) и его медиана равна \(5\).
Во втором примере можно один раз увеличить второе число, а также два раза увеличить третье и пятое. Тогда ответ будет равен \(3\).
В третьем примере можно сделать четыре операции, чтобы увеличить первый, четвёртый, шестой и седьмой элемент, тогда массив будет равен \([5, 1, 2, 5, 3, 5, 5]\) и медиана будет равна \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 3 5
|
5
|
|
2
|
5 5
1 2 1 1 1
|
3
|
|
3
|
7 7
4 1 2 4 3 4 4
|
5
|