CF1661D.Progressions Covering

You are given two arrays: an array $a$ consisting of $n$ zeros and an array $b$ consisting of $n$ integers.

You can apply the following operation to the array $a$ an arbitrary number of times: choose some subsegment of $a$ of length $k$ and add the arithmetic progression $1, 2, \ldots, k$ to this subsegment — i. e. add $1$ to the first element of the subsegment, $2$ to the second element, and so on. The chosen subsegment should be inside the borders of the array $a$ (i.e., if the left border of the chosen subsegment is $l$, then the condition $1 \le l \le l + k - 1 \le n$ should be satisfied). Note that the progression added is always $1, 2, \ldots, k$ but not the $k, k - 1, \ldots, 1$ or anything else (i.e., the leftmost element of the subsegment always increases by $1$, the second element always increases by $2$ and so on).

Your task is to find the minimum possible number of operations required to satisfy the condition $a_i \ge b_i$ for each $i$ from $1$ to $n$. Note that the condition $a_i \ge b_i$ should be satisfied for all elements at once.

你有两个数组：一个由 $n$ 个零组成的数组 $a$，以及一个由 $n$ 个整数组成的数组 $b$。

你可以对数组 $a$ 执行任意多次如下操作：选择 $a$ 的一个长度为 $k$ 的子段，并向该子段加上等差数列 $1, 2, \ldots, k$ —— 即向子段的第一个元素加 $1$，第二个元素加 $2$，依此类推。所选子段必须完全位于数组 $a$ 的边界内（即若所选子段的左端点为 $l$，则需满足 $1 \le l \le l + k - 1 \le n$）。注意，每次所加的等差数列恒为 $1, 2, \ldots, k$，而非 $k, k-1, \ldots, 1$ 或其他形式（即子段最左侧元素总是增加 $1$，第二个元素总是增加 $2$，以此类推）。

你的任务是求出满足条件 $a_i \ge b_i$（对每个 $i = 1, 2, \ldots, n$）所需的最少操作次数。注意，该条件需对所有元素同时成立。

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$) — the number of elements in both arrays and the length of the subsegment, respectively.

The second line of the input contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^{12}$), where $b_i$ is the $i$-th element of the array $b$.

输入的第一行包含两个整数 $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$ 个元素。

Print one integer — the minimum possible number of operations required to satisfy the condition $a_i \ge b_i$ for each $i$ from $1$ to $n$.

输出一个整数——满足对每个 $i$（从 $1$ 到 $n$）都有 $a_i \ge b_i$ 所需的最少操作次数。

Consider the first example. In this test, we don't really have any choice, so we need to add at least five progressions to make the first element equals $5$. The array $a$ becomes $[5, 10, 15]$.

Consider the second example. In this test, let's add one progression on the segment $[1; 3]$ and two progressions on the segment $[4; 6]$. Then, the array $a$ becomes $[1, 2, 3, 2, 4, 6]$.

考虑第一个例子。在该测试中，我们实际上没有任何选择，因此至少需要添加五个等差数列，使得第一个元素等于 $5$。此时数组 $a$ 变为 $[5, 10, 15]$。

考虑第二个例子。在该测试中，我们在区间 $[1; 3]$ 上添加一个等差数列，在区间 $[4; 6]$ 上添加两个等差数列。此时数组 $a$ 变为 $[1, 2, 3, 2, 4, 6]$。