Description

They are now at a barrier formation that connects the ancient and modern worlds. Generally, even gods cannot traverse time and space. However, lin_toto gave them a hint and revealed the secret of this formation. He told kkksc03 and lzn that as long as they work together, they can change their destiny and break the shackles of the barrier.

lin_toto led them to the front of the formation. What lay before them was a huge yet damaged wall, composed of several consecutive groups of magical bricks (each magical brick is a cube of size $1\times1\times1$), and the heights of these groups are all different. From experience, only by making the heights of at least $K$ consecutive groups that form this wall equal can they break through the entrance of the formation, summon help from the divine realm, and traverse time and space.

They can perform the following operations: remove one brick from the wall, or take one brick from a nearby pile of magical bricks (assume an unlimited supply) and place it on the wall. Each brick moved consumes one unit of energy from kkksc03 and lzn. lzn wants to minimize the total energy consumed.

Now kkksc03 has come to you with this problem. Can you help him compute the minimum energy required?

Input Format

One line with two positive integers $N, K$. Then $N$ lines follow, each representing the height $H_i$ of a group of magical bricks.

Output Format

A single integer, the minimum energy required.

5 2
5
4
1
2
3

1

Hint

For $10\%$ of the testdata, $1 \le N \le 10$, $2 \le K \le N$, $0 \le H_i \le N$.

For $20\%$ of the testdata, $K = 2$.

For $40\%$ of the testdata, $1 \le N \le 500$, $2 \le K \le N$, $0 \le H_i \le N$.

For $80\%$ of the testdata, $1 \le N \le 10^5$, $2 \le K \le N$, $0 \le H_i \le 10^6$.

For $100\%$ of the testdata, $1 \le N \le 5 \times 10^5$, $2 \le K \le N$, $0 \le H_i \le 10^{12}$, and all $H_i$ are distinct.

Translated by ChatGPT 5