问题描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\\dots,A_N)$。你可以执行以下操作任意次数（可能为零）。

• 选择一个整数 $i$，满足 $1 \\le i \\le N$，将 $A_i$ 增加或减少 $1$。

你的目标是使至少 $M$ 个整数 $i(3 \\le i \\le N)$ 满足 $A_1 \\le A_i \\le A_2$。找到达成这一目标所需的最小操作次数。

约束条件

• $3 \\le N \\le 2 \\times 10^5$
• $1 \\le M \\le N-2$
• $1 \\le A_i \\le 10^9$

输入

从标准输入读取输入，其格式如下：

$N$ $M$ $A_1$ $A_2$ $\\dots$ $A_N$

输出

打印需要的最小操作次数。

示例输入 1

3 1
2 3 5

示例输出 1

2

你可以通过以下操作使得不少于一个整数 $i(3 \\le i \\le N)$ 满足 $A_1 \\le A_i \\le A_2$。

• 选择 $i=3$，将 $A_i$ 减少 $1$。
• 选择 $i=2$，将 $A_i$ 增加 $1$。

由于不可能用少于 $2$ 次操作达到目标，所以答案是 $2$。

示例输入 2

5 2
1 4 2 3 5

示例输出 2

0

你可能已经从一开始就实现了目标。

示例输入 3

8 5
15 59 64 96 31 17 88 9

示例输出 3

35