Progressions Covering
Contest: Educational Codeforces Round 126 (Rated for Div. 2)
Difficulty rating: 1900
Tags: data structures, greedy

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.

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
3 3
5 4 6

Example output:
5

Example input:
6 3
1 2 3 2 2 3

Example output:
3

Editorial:
Let's solve the problem greedily. But not from the beginning, because if we solve it from the beginning, we can't be sure what option is more optimal for the next elements (e.g. for the second element it is not clear if we need to add $$$2$$$ to it starting our segment from the first position or add $$$1$$$ to it starting our segment from the second position). So, let's solve the problem from right to left, then anything becomes clearer.
Actually, let's operate with the array $$$b$$$ and decrease its elements instead of using some other array. Let's carry some variables: $$$sum$$$, $$$cnt$$$ and the array $$$closed$$$ of length $$$n$$$ (along with the answer). The variable $$$sum$$$ means the value we need to subtract from the current element from currently existing progressions, $$$cnt$$$ is the number of currently existing progressions, and $$$closed_i$$$ means the number of progressions that will end at the position $$$i+1$$$ (i.e. will not add anything from the position $$$i$$$ and further to the left).
When we consider the element $$$i$$$, firstly let's fix $$$sum$$$ (decrease it by $$$cnt$$$). Then, let's fix $$$cnt$$$ (decrease it by $$$closed_i$$$). Then, let's decrease $$$b_i$$$ by $$$sum$$$, and if it becomes less than or equal to zero, just proceed. Otherwise, the number by which we can decrease the $$$i$$$-th element with one progression, equals to $$$el = min(k, i + 1)$$$ (zero-indexed). Then the number of progressions we need to satisfy this element is $$$need = \lceil\frac{b_i}{el}\rceil$$$. Let's add this number to the answer, increase $$$sum$$$ by $$$el \cdot need$$$, increase $$$cnt$$$ by $$$need$$$, and if $$$i - el \ge 0$$$ then we need to end these progressions somewhere, so let's add $$$need$$$ to $$$closed_{i - el}$$$.
Time complexity: $$$O(n)$$$.