← 返回题目列表

AtCoder · arc138_a

A. 更大的分数

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有一个长度为的整数序列 N: A=(A_1,A_2,\cdots,A_N)。 下面在这个问题中,让 分数 of A 是第一个的总和 K 条款 A。 另外,让 s 是序列的分数 A 在输入中给出。

您可以多次执行以下操作。

  • 选择两个相邻元素 A 并交换它们。

你的目标是至少获得分数 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)

一次操作无法实现该目标,因此所需的最少操作次数为 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