题目描述

長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N)$ があります． 以降この問題では，$A$ の先頭 $K$ 項の和を スコア と呼ぶことにします． また，入力で与えられた $A$ のスコアを $s$ と置くことにします．

あなたは，以下の操作を好きな回数繰り返すことができます．

• $A$ のある隣接する $2$ 要素を選び，それらの値を入れ替える．

あなたの目標は，スコアを $s+1$ 以上にすることです． 目標が達成可能であるかどうか判定し，また可能であるなら必要な最小の操作回数を求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

目標が達成可能でない場合，-1 を出力せよ． 可能である場合，必要な最小の操作回数を出力せよ．

题目大意

给定 $n$ 个数，你可以交换任意相邻的两个数，使的原数组的前 $k$ 个数字的和严格小于任意次交换后的前 $k$ 个数字的和，问最小操作次数。

4 2
2 1 1 2

2

3 1
3 2 1

-1

20 13
90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054

13

提示

制約

• $2\ \leq\ N\ \leq\ 4\ \times\ 10^5$
• $1\ \leq\ K\ \leq\ N-1$
• $1\ \leq\ A_i\ \leq\ 10^9$
• 入力される値はすべて整数

Sample Explanation 1

まず，$s=2+1=3$ です． 以下のように操作することで，スコアを $4$ 以上にすることができます． - $(2,1,1,2)\ \to\ (A_3$ と $A_4$ の値を入れ替える $)\to\ (2,1,2,1)\ \to\ (A_2$ と $A_3$ の値を入れ替える $)\to\ (2,2,1,1)$ $1$ 回の操作では目標を達成できないため，必要な最小の操作回数は $2$ になります．