201380: [AtCoder]ARC138 A - Larger Score

Memory Limit:1024 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: