男孩 Vasya 非常喜欢旅行。尤其是乘坐飞机给他带来了非凡的乐趣。他正要飞往另一个城市,但跑道被厚厚的积雪覆盖,需要清理。
跑道可以表示为 $$$n$$$ 连续部分,编号从 $$$1$$$ 到 $$$n$$$。暴风雪相当猛烈,但已经停止了,因此 Vasya 计算出第 $$$i$$$ 部分被 $$$a_i$$$ 米厚的雪覆盖。对于这种情况,机场有一台扫雪机,其工作方式相当不寻常。一分钟内,扫雪机可以执行以下操作:
- 选择长度不超过 $$$d$$$ 的连续路段,并从积雪最多的部分清除一米的积雪。
形式上,可以选择 $$$1 \le l \le r \le n$$$ ($$$r - l + 1 \le d$$$)。之后,计算$$$c = \max \{ a_l, a_{l + 1}, \ldots , a_r \}$$$,如果$$$c \gt 0$$$,则对于所有$$$i \colon l \le i \le r$$$,使得$$$a_i = c$$$,$$$a_i$$$的值减1。
Vasya 已经为飞行做了很长时间的准备,他想了解他还剩下多少时间才能等到所有路段的积雪完全清除。换句话说,需要计算扫雪机对于从$$$1$$$到$$$n$$$的所有$$$i$$$达到$$$a_i = 0$$$所需的最小分钟数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$1 \le n \le 5 \cdot 10^5, 1 \le d \le n$$$) — 跑道上的路段数以及扫雪机可以选择的路段的最大长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 部分的积雪米数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$,扫雪机实现 $$$a_i = 0$$$ 所需的最小分钟数。
示例
输入复制
25 21 5 2 1 23 11000000000 1000000000 1000000000
输出复制
8 3000000000
注意
在第一个测试用例中,存在最佳操作顺序。首先,选择段 $$$[2, 3]$$$ 四次。经过三次操作,$$$a_2$$$将变成$$$2$$$,数组$$$a$$$将变为$$$[1, 2, 2, 1, 2]$$$。第四次操作后,数组 $$$a$$$ 将变为 $$$[1, 1, 1, 1, 2]$$$。接下来,可以通过选择段 $$$[1, 2]$$$、$$$[3, 3]$$$、$$$[5, 5]$$$ 和 $$$[4, 5]$$$(按确切顺序)将数组转换为零。
在第二个测试用例中,$$$d = 1$$$,这意味着每个部分都独立于其他部分进行清除,并且答案等于所有$$$a_i$$$的总和。 数组 $$$c$$$ 中值 $$$x$$$ 的