配点 : $400$ 点

問題文

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

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

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

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

制約

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

入力

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

$N$ $K$

$A_1$ $A_2$ $\cdots$ $A_N$

出力

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

4 2
2 1 1 2

2

まず，$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$ になります．

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