/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。あなたは、以下の操作を好きな回数（0 回でもよい）行うことが出来ます。
- 1 \le i \le N を満たす整数 i を 1 個選び、A_i を 1 増やすか 1 減らす。
あなたの目標は、A_1 \le A_i \le A_2 を満たす整数 i(3 \le i \le N) の個数を M 個以上にすることです。目標を達成するために必要な最小の操作回数を求めてください。
制約
- 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
以下のように操作を行うことで A_1 \le A_i \le A_2 を満たす整数 i(3 \le i \le N) の個数を 1 個以上に出来ます。
- i=3 を選び、A_i を 1 減らす。
- i=2 を選び、A_i を 1 増やす。
1 回以下の操作回数で目標を達成することは出来ないため、答えは 2 です。
入力例 2
5 2 1 4 2 3 5
出力例 2
0
始めから目標を達成していることもあります。
入力例 3
8 5 15 59 64 96 31 17 88 9
出力例 3
35
Score : 400 points
Problem Statement
You are given an integer sequence of length N: A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).
- Choose an integer i such that 1 \le i \le N, and increase or decrease A_i by 1.
Your goal is to make at least M integers i(3 \le i \le N) satisfy A_1 \le A_i \le A_2. Find the minimum number of operations required to achieve this goal.
Constraints
- 3 \le N \le 2 \times 10^5
- 1 \le M \le N-2
- 1 \le A_i \le 10^9
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the minimum number of operations required.
Sample Input 1
3 1 2 3 5
Sample Output 1
2
You can make not less than one integer i(3 \le i \le N) satisfy A_1 \le A_i \le A_2 by performing the operation as follows.
- Choose i=3, and decrease A_i by 1.
- Choose i=2, and increase A_i by 1.
Since it is impossible to achieve the goal with less than 2 operation, the answer is 2.
Sample Input 2
5 2 1 4 2 3 5
Sample Output 2
0
You may already have achieved the goal from the start.
Sample Input 3
8 5 15 59 64 96 31 17 88 9
Sample Output 3
35