Вам дан массив $$$a$$$ из $$$n$$$ целых чисел, где $$$n$$$ нечётно. Вы можете проделать с массивом следующую операцию:
Вы хотите сделать медиану массива максимально большой, используя не более $$$k$$$ операций.
Медианой нечётного по размеру массива называется средний элемент, если массив отсортировать по неубыванию. Например, медианой массива $$$[1, 5, 2, 3, 5]$$$ является $$$3$$$.
Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n$$$ нечётно, $$$1 \le k \le 10^9$$$) — количество элементов в массиве и наибольшее возможное количество операций, которое можно сделать.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
Выведите одно целое число — наибольшую возможную медиану после всех операций.
3 2 1 3 5
5
5 5 1 2 1 1 1
3
7 7 4 1 2 4 3 4 4
5
В первом примере можно два раза увеличить второй элемент. Тогда массив будет равен $$$[1, 5, 5]$$$ и его медиана равна $$$5$$$.
Во втором примере можно один раз увеличить второе число, а также два раза увеличить третье и пятое. Тогда ответ будет равен $$$3$$$.
В третьем примере можно сделать четыре операции, чтобы увеличить первый, четвёртый, шестой и седьмой элемент, тогда массив будет равен $$$[5, 1, 2, 5, 3, 5, 5]$$$ и медиана будет равна $$$5$$$.
| Codeforces Round 577 (Div. 2) |
|---|
| Закончено |
