给定两个数组:一个由 $$$n$$$ 零组成的数组 $$$a$$$ 和一个由 $$$n$$$ 整数组成的数组 $$$b$$$。
您可以对数组 $$$a$$$ 应用以下操作任意次数:选择 $$$a$$$ 长度为 $$$k$$$ 的某个子段,并将算术级数 $$$1, 2, \ldots, k$$$ 添加到该子段 - i. e.将 $$$1$$$ 添加到子段的第一个元素,将 $$$2$$$ 添加到第二个元素,依此类推。所选子段应位于数组 $$$a$$$ 的边界内(即,如果所选子段的左边界为 $$$l$$$,则应满足条件 $$$1 \le l \le l + k - 1 \le n$$$)。请注意,添加的级数始终是 $$$1, 2, \ldots, k$$$,而不是 $$$k, k - 1, \ldots, 1$$$ 或其他任何内容(即,子段的最左侧元素始终增加 $$$1$$$,第二个元素始终增加 $$$2$$$,依此类推)。
您的任务是找到从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$ 满足条件 $$$a_i \ge b_i$$$ 所需的最小可能操作数。请注意,所有元素都应同时满足条件 $$$a_i \ge b_i$$$。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) — 分别是两个数组中的元素数量和子段的长度。
输入的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^{12}$$$),其中 $$$b_i$$$ 是数组 $$$b$$$ 的第 $$$i$$$ 个元素。
输出
打印一个整数 — 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,满足条件 $$$a_i \ge b_i$$$ 所需的最小可能操作数。
示例
输入 #1
3 3 5 4 6
输出 #1
5
输入 #2
6 3 1 2 3 2 2 3
输出 #2
3
输入 #3
6 3 1 2 4 1 2 3
输出 #3
3
输入#4
7 3 50 17 81 25 42 39 96
输出#4
92
注意
考虑第一个例子。在这个测试中,我们实际上没有任何选择,因此我们需要添加至少五个级数以使第一个元素等于 $$$5$$$。数组 $$$a$$$ 变为 $$$[5, 10, 15]$$$。
考虑第二个例子。在此测试中,我们在 $$$[1; 段上添加一个进程3]$$$ 和 $$$[4 段上的两个级数; 6]$$$。然后,数组 $$$a$$$ 变为 $$$[1, 2, 3, 2, 4, 6]$$$。