← 返回题目列表

Codeforces · 1876/F

F. 不定的小丑鱼

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

Pak Chanek 刚刚买了一个空鱼缸,他一直梦想着在里面装满他最喜欢的鱼——小丑鱼。 Pak Chanek 喜欢小丑鱼,因为它们能够根据需要改变性别。由于他的鱼缸太大,Pak Chanek 想要购买 $$$k$$$ 小丑鱼来填满鱼缸。

Pak Chanek 前往当地的鱼店。店里提供$$$n$$$小丑鱼,编号从$$$1$$$到$$$n$$$,其中$$$i$$$的小丑鱼大小为$$$a_i$$$。最初,商店中的每条小丑鱼都没有指定的性别,但有能力被指定为两种可能的小丑鱼性别:雌性或雄性。

商店有 Pak Chanek 购买小丑鱼应遵循的程序。店主会依次指着每条小丑鱼,从 $$$1$$$ 到 $$$n$$$,对于每条小丑鱼,她都会询问 Pak Chanek 是否购买。每次 Pak Chanek 被问到时,他必须先声明是否购买当前询问的小丑鱼,然后店主才会转向下一条小丑鱼。如果 Pak Chanek 声明购买当前要求的小丑鱼,他还必须立即声明分配给该小丑鱼的性别。在为当前询问的小丑鱼分配性别时,必须满足以下条件:

- 如果 Pak Chanek 将其指定为雌性,并且他之前购买过雌性小丑鱼,那么当前的小丑鱼的大小必须比上一个雌性小丑鱼正好 $$$1$$$ 大。
- 如果 Pak Chanek 将其指定为雄性,并且他之前购买过一条雄性小丑鱼,那么当前这条小丑鱼的大小必须恰好比上一条雄性小丑鱼小 $$$1$$$。

Pak Chanek 想要购买 $$$k$$$ 小丑鱼,这样:

- 至少有一条雌性小丑鱼和一条雄性小丑鱼。
- Pak Chanek 购买的 $$$k$$$ 小丑鱼中,雌性小丑鱼的平均大小与雄性小丑鱼的平均大小相同。

令 $$$l$$$ 和 $$$r$$$ 分别为 Pak Chanek 购买的小丑鱼的最小和最大指数。 $$$r-l$$$ 的最小可能值是多少?

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq k \leq n \leq 2\cdot10^5$$$) — 商店里小丑鱼的数量和 Pak Chanek 必须购买的小丑鱼的数量。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) — 每条小丑鱼的大小。

输出

一个整数,表示 $$$r-l$$$ 的最小可能值。如果不可能准确购买 $$$k$$$ 小丑鱼并满足问题条件,则打印 $$$-1$$$。

示例

输入 #1

9 6
2 4 2 3 2 4 1 3 4

输出 #1

6

输入 #2

6 6
2 6 5 2 6 5

输出 #2

-1

输入 #3

5 4
1 2 3 4 5

输出 #3

-1

注意

在第一个示例中,Pak Chanek 可以执行以下操作:

1. 不要购买小丑鱼$$$1$$$。
2. 购买小丑鱼 $$$2$$$ 并将其指定为雄性。
3. 购买小丑鱼 $$$3$$$ 并将其指定为雌性。
4. 购买小丑鱼 $$$4$$$ 并将其指定为雄性。
5. 购买小丑鱼 $$$5$$$ 并将其指定为雄性。
6. 不要购买小丑鱼$$$6$$$。
7. 购买小丑鱼 $$$7$$$ 并将其指定为雄性。
8. 购买小丑鱼 $$$8$$$ 并将其指定为雌性。
9. 不要购买小丑鱼$$$9$$$。

然后,我们得到:

- Pak Chanek 购买的 $$$2$$$ 雌性小丑鱼的平均尺寸为 $$$\frac{2+3}{2} = 2.5$$$。
- Pak Chanek 购买的 $$$4$$$ 雄性小丑鱼的平均尺寸为 $$$\frac{4+3+2+1}{4} = 2.5$$$。
- $$$l=2$$$,$$$r=8$$$,$$$r-l=6$$$。

没有更好的策略。