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

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

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


-----Examples-----

Input
3 3
5 4 6
Output
5
Input
6 3
1 2 3 2 2 3
Output
3
Input
6 3
1 2 4 1 2 3
Output
3
Input
7 3
50 17 81 25 42 39 96
Output
92


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

Source: codeforces | Difficulty: HARD
Tags: Data structures

Greedy algorithms


Solutions:
def main():
	(n, k) = map(int, input().split())
	b = list(map(int, input().split()))
	temp = 0
	operations = [0] * n
	last = 0
	for i in range(n - 1, k - 1, -1):
		now = 0
		if i != n - 1:
			last -= temp
			now = last
			if i + k >= n:
				pass
			else:
				temp -= operations[i + k]
		delta = b[i] - now
		if delta <= 0:
			continue
		else:
			operations[i] = (delta + k - 1) // k
			temp += operations[i]
			last = operations[i] * k + now
	m = 0
	need = [0] * k
	for i in range(k - 1, -1, -1):
		if i != n - 1:
			last -= temp
			need[i] = max(0, b[i] - last)
			if i + k >= n:
				pass
			else:
				temp -= operations[i + k]
		else:
			need[i] = max(0, b[i])
	for i in range(k):
		m = max(m, (need[i] + i) // (i + 1))
	print(sum(operations) + m)
main()


import math

def progressions_covering():
	(n, k) = [int(x) for x in input().split(' ')]
	b = [int(x) for x in input().split(' ')]
	result = 0
	count = 0
	summ = 0
	a = [0 for x in range(n)]
	for i in range(n - 1, -1, -1):
		summ -= count
		count -= a[i]
		b[i] -= summ
		if b[i] <= 0:
			continue
		el = min(i + 1, k)
		needed = math.ceil(b[i] / el)
		summ += needed * el
		count += needed
		result += needed
		if i - el >= 0:
			a[i - el] += needed
	print(result)
progressions_covering()


(n, k) = [*map(int, input().split())]
b = [*map(int, input().split())]
d = [0] * n
s = total = 0
for i in range(n - 1, -1, -1):
	b[i] -= total
	if b[i] > 0:
		dd = min(k, i + 1)
		d[i] = (b[i] + dd - 1) // dd
	s += d[i] - (d[i + k] if i + k < n else 0)
	total += d[i] * dd - s
print(sum(d))


(n, k) = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
result = 0
count = 0
summ = 0
closed = [0 for x in range(n)]
for i in range(n - 1, -1, -1):
	summ -= count
	count -= closed[i]
	b[i] -= summ
	if b[i] <= 0:
		continue
	el = min(i + 1, k)
	needed = int((b[i] + el - 1) / el)
	summ += needed * el
	count += needed
	result += needed
	if i - el >= 0:
		closed[i - el] += needed
print(result)


from math import ceil
(n, k) = [int(x) for x in input().split(' ')]
array_b = [int(x) for x in input().split(' ')]
soma_acumulada = 0
ops_acumulado = 0
total_ops = 0
fim_progressao = [0] * n
for i in reversed(range(n)):
	soma_acumulada -= ops_acumulado
	ops_acumulado -= fim_progressao[i]
	array_b[i] -= soma_acumulada
	if array_b[i] <= 0:
		continue
	delta = min(k, i + 1)
	minimo_ops_para_i = ceil(array_b[i] / delta)
	total_ops += minimo_ops_para_i
	soma_acumulada += delta * minimo_ops_para_i
	ops_acumulado += minimo_ops_para_i
	if i - delta >= 0:
		fim_progressao[i - delta] += minimo_ops_para_i
print(total_ops)


(n, k) = map(int, input().split())
b = list(map(int, input().split()))
(ans, sum, cnt) = (0, 0, 0)
closed = [0] * n
for i in range(n - 1, -1, -1):
	sum -= cnt
	b[i] -= sum
	cnt -= closed[i]
	if b[i] <= 0:
		continue
	delta = min(i + 1, k)
	x = (b[i] + delta - 1) // delta
	cnt += x
	sum += x * delta
	ans += x
	closed[i - k] += x
print(ans)


if True:
	(n, k) = list(map(int, input().split()))
	b = list(map(int, input().split()))
	closed = [0] * len(b)
	sum = 0
	cnt = 0
	ans = 0
	for i in range(len(b) - 1, -1, -1):
		sum -= cnt
		cnt -= closed[i]
		b[i] -= sum
		if b[i] <= 0:
			continue
		el = min(k, i + 1)
		f = b[i] // el + (1 if b[i] % el != 0 else 0)
		sum += f * el
		cnt += f
		ans += f
		if i >= k:
			closed[i - k] += f
	print(ans)


(n, k) = map(int, input().split())
b = list(map(int, input().split()))
(ans, a) = (0, 0)
d2 = [0] * n
d = 0
for i in range(n - 1, -1, -1):
	d += d2[i]
	a += d
	if a >= b[i]:
		continue
	v = min(k, i + 1)
	x = (b[i] - a + v - 1) // v
	a += v * x
	ans += x
	if i > 0:
		d2[i - 1] -= x
		if i - k - 1 >= 0:
			d2[i - 1 - k] += x
print(ans)