题目描述

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

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

你的目标是，使得满足 $A_1 \leq A_i \leq A_2$ 的整数 $i$（$3 \leq i \leq N$）的个数不少于 $M$。请你求出达成目标所需的最小操作次数。

输入格式

输入从标准输入中按以下格式给出。

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

输出格式

输出达成目标所需的最小操作次数。

样例 1

输入

3 1
2 3 5

输出

2

样例 2

输入

5 2
1 4 2 3 5

输出

0

样例 3

输入

8 5
15 59 64 96 31 17 88 9

输出

35

说明/提示

限制条件

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

样例解释 1

可以通过如下操作使得满足 $A_1 \leq A_i \leq A_2$ 的整数 $i$（$3 \leq i \leq N$）的个数不少于 $1$：

• 选择 $i=3$，将 $A_i$ 减少 $1$。
• 选择 $i=2$，将 $A_i$ 增加 $1$。 由于无法用 $1$ 次或更少的操作达成目标，所以答案为 $2$。

样例解释 2

有时一开始就已经达成目标。

由 ChatGPT 4.1 翻译