A - Larger Score Editorial /

Time Limit: 3 sec / Memory Limit: 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_3A_4 の値を入れ替える )\to (2,1,2,1) \to (A_2A_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