A - Larger Score 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 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 を出力せよ． 可能である場合，必要な最小の操作回数を出力せよ．

入力例 1

4 2
2 1 1 2

出力例 1

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

入力例 2

3 1
3 2 1

出力例 2

-1

入力例 3

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

出力例 3

13

Score : 400 points

Problem Statement

We have an integer sequence of length N: A=(A_1,A_2,\cdots,A_N). Below in this problem, let the score of A be the sum of the first K terms of A. Additionally, let s be the score of the sequence A given in input.

You can do the following operation any number of times.

  • Choose two adjacent elements of A and swap them.

Your objective is to make the score at least s+1. Determine whether the objective is achievable. If it is, find the minimum number of operations needed to achieve it.

Constraints

  • 2 \leq N \leq 4 \times 10^5
  • 1 \leq K \leq N-1
  • 1 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_N

Output

If the objective is not achievable, print -1. If it is achievable, print the minimum number of operations needed to achieve it.

Sample Input 1

4 2
2 1 1 2

Sample Output 1

2

We have s=2+1=3. The following sequence of operations makes the score at least 4.

  • (2,1,1,2) \to (swap A_3 and A_4)\to (2,1,2,1) \to (swap A_2 and A_3)\to (2,2,1,1)

The objective is not achievable in one operation, so the minimum number of operations needed is 2.

Sample Input 2

3 1
3 2 1

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

13