CF1876F Indefinite Clownfish

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$ 条小丑鱼，并且满足以下条件： - 至少要有一条雌性小丑鱼和一条雄性小丑鱼。 - 在买下的 $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$。

在第一个样例中，Pak Chanek 可以这样做： 1. 不买第 $1$ 条小丑鱼。 2. 买第 $2$ 条小丑鱼并指定为雄性。 3. 买第 $3$ 条小丑鱼并指定为雌性。 4. 买第 $4$ 条小丑鱼并指定为雄性。 5. 买第 $5$ 条小丑鱼并指定为雄性。 6. 不买第 $6$ 条小丑鱼。 7. 买第 $7$ 条小丑鱼并指定为雄性。 8. 买第 $8$ 条小丑鱼并指定为雌性。 9. 不买第 $9$ 条小丑鱼。 此时： - 买下的 $2$ 条雌性小丑鱼的平均体型为 $\frac{2+3}{2}=2.5$。 - 买下的 $4$ 条雄性小丑鱼的平均体型为 $\frac{4+3+2+1}{4}=2.5$。 - $l=2$，$r=8$，$r-l=6$。 没有更优的方案了。 由 ChatGPT 4.1 翻译