题目描述

我们有一个长度为 $N$ 的整数序列：$A=(A_1,A_2,\cdots,A_N)$。在本问题中，定义 $A$ 的分数为 $A$ 的前 $K$ 个元素的和。另外，设输入中给定的序列 $A$ 的分数为 $s$。

你可以进行以下操作任意次数。

• 选择 $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