F. Башенные массивы
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Массив $$$b = [b_1, b_2, \ldots, b_m]$$$ длины $$$m$$$ называется $$$p$$$-башенным, если существует индекс $$$i$$$ ($$$1\le i\le m$$$) такой, что для каждого индекса $$$j$$$ ($$$1 \le j \le m$$$) выполняется следующее условие: $$$$$$b_j \ge p - |i - j|.$$$$$$

Дан массив $$$a = [a_1, a_2, \ldots, a_n]$$$ длины $$$n$$$, вы можете удалить из него не более $$$k$$$ элементов. Определите максимальное значение $$$p$$$, для которого оставшийся массив может быть сделан $$$p$$$-башенным.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$0 \le k < n \le 2 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — максимальное значение $$$p$$$, для которого оставшийся массив может быть сделан $$$p$$$-башенным.

Пример
Входные данные
6
5 0
2 1 4 5 2
5 3
2 1 4 5 2
6 1
1 2 3 4 5 1
11 6
6 3 8 5 8 3 2 1 2 7 1
14 3
3 2 3 5 5 2 6 7 4 8 10 1 8 9
2 0
1 1
Выходные данные
3
5
5
7
9
1
Примечание

В первом наборе входных данных вы не можете удалить ни один элемент. Массив остается равен $$$[2, 1, 4, \color{red}{5}, 2]$$$ и он является p-башенным для $$$p = 3$$$ при выборе $$$i = 4$$$:

  • $$$a_1 = 2 \ge p - |i - 1| = 3 - |4 - 1| = 0$$$;
  • $$$a_2 = 1 \ge p - |i - 2| = 3 - |4 - 2| = 1$$$;
  • $$$a_3 = 4 \ge p - |i - 3| = 3 - |4 - 3| = 2$$$;
  • $$$a_4 = 5 \ge p - |i - 4| = 3 - |4 - 4| = 3$$$;
  • $$$a_5 = 2 \ge p - |i - 5| = 3 - |4 - 5| = 2$$$.

Во втором наборе входных данных вы можете удалить первый, второй и пятый элементы, чтобы получить массив $$$[4, \color{red}{5}]$$$. Очевидно, что полученный массив является p-башенным для $$$p = 5$$$ при выборе $$$i = 2$$$.