← 返回题目列表

AtCoder · arc163_b

B. 最喜欢的游戏

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

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

  • 选择一个整数 i 这样 1 \le i \le N,并增加或减少 A_i by 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

可以使不少于1个整数 i(3 \le i \le N) 满足 A_1 \le A_i \le A_2 通过执行如下操作。

  • 选择 i=3,并减少 A_i by 1.
  • 选择 i=2,并增加 A_i by 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