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$$$。
没有更好的策略。