A15059. 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.

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$ .

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$ .

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]$ .