На одной из площадок олимпиады по физкультуре «Мышечные технологии» есть две аудитории. Между ними расположены $$$n$$$ столов, на которых лежат пиццы, на $$$i$$$-м столе находятся $$$a_i$$$ пицц. При этом первая аудитория находится перед первым столом, а вторая — после последнего стола.
По завершении олимпиады, каждую секунду, начиная с первой, ровно один участник выходит из каждой аудитории, находит ближайший к нему стол, на котором еще лежит хотя бы одна пицца, подходит к нему и ест ровно одну пиццу, после чего сразу же уходит на разбор. Участники очень старались на олимпиаде, поэтому проголодались. Можно считать, что они моментально подходят к столу и едят пиццу.
В разных аудиториях участникам были предложены разные задачи. Поэтому, если участник из первой аудитории видит, как участник из второй аудитории ест пиццу со стола на расстоянии не больше $$$k$$$, он немедленно начнёт обсуждать с ним задачи. Или же, более формально, пусть для участника из первой аудитории $$$x$$$ — номер ближайшего к нему стола с пиццей, а $$$y$$$ — номер стола с пиццей для участника из второй аудитории, тогда, если $$$y - x \leq k$$$, то они немедленно начнут обсуждать задачи.
Организаторы устали после тура и хотят отдохнуть в тишине. Им известно, что как только участники начнут обсуждать задачи, их покой будет нарушен. Помогите организаторам определить, через сколько секунд после завершения олимпиады начнётся обсуждение задач.
Данная задача состоит из нескольких наборов входных данных. В первой строке задано единственное число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Затем идет их описание.
В первой строке каждого набора входных данных заданы два числа $$$n, k$$$ ($$$2 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq n - 1$$$) — количество столов с пиццами между аудиториями и расстояние, на котором участники начнут обсуждать задачи.
В следующей строке заданы целые числа $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — количества пицц на столах.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите ровно одно число — минимальное количество секунд, после которых участники начнут обсуждать задачи.
Можно показать, что в указанных ограничениях обсуждение задач гарантированно произойдёт.
35 21 1 1 1 25 31 1 1 1 23 13 1 4
3 2 4
В первых двух наборах входных данных массив количеств пицц имеет вид $$$[1, 1, 1, 1, 2]$$$.
На первой секунде участник из первой аудитории взял пиццу под номером $$$1$$$, а из второй $$$5$$$, после этого массив количеств пицц имеет вид $$$[0, 1, 1, 1, 1]$$$.
На второй секунде участник из первой аудитории взял пиццу под номером $$$2$$$, а из второй $$$5$$$, после этого массив количеств пицц имеет вид $$$[0, 0, 1, 1, 0]$$$.
На третьей секунде участник из первой аудитории взял пиццу под номером $$$3$$$, а из второй $$$4$$$, после этого массив количеств пицц имеет вид $$$[0, 0, 0, 0, 0]$$$.
В первом наборе входных данных $$$k = 2$$$, поэтому на третьей секунде они начнут обсуждать задачи, так как $$$4 - 3 \leq k$$$.
Во втором наборе входных данных они начнут обсуждать задачи на второй секунде.
В третьем наборе входных данных они начнут обсуждать задачи на четвёртой секунде.
