310726: CF1876F. Indefinite Clownfish

F. Indefinite Clownfishtime limit per test3.5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Pak Chanek has just bought an empty fish tank and he has been dreaming to fill it with his favourite kind of fish, clownfish. Pak Chanek likes clownfish because of their ability to change their genders on demand. Because of the size of his fish tank, Pak Chanek wants to buy exactly $k$ clownfish to fill the tank.

Pak Chanek goes to the local fish shop. The shop provides $n$ clownfish numbered from $1$ to $n$, with clownfish $i$ having a size of $a_i$. Initially, every clownfish in the store does not have an assigned gender, but has the ability to be assigned to two possible clownfish genders, female or male.

The store has a procedure which Pak Chanek should follow to buy clownfish. The shop owner will point at each clownfish sequentially from $1$ to $n$ and for each clownfish, she asks Pak Chanek whether to buy it or not. Each time Pak Chanek is asked, he must declare whether to buy the currently asked clownfish or not, before the shop owner moves on to the next clownfish. If Pak Chanek declares to buy the currently asked clownfish, he must also declare the gender to be assigned to that clownfish immediately. When assigning the gender for the currently asked clownfish, the following conditions must be satisfied:

• If Pak Chanek assigns it to be female and he has bought a female clownfish before, then the size of the current one must be exactly $1$ bigger than the last female one.
• If Pak Chanek assigns it to be male and he has bought a male clownfish before, then the size of the current one must be exactly $1$ smaller than the last male one.

Pak Chanek wants to buy exactly $k$ clownfish such that:

• There is at least one female clownfish and one male clownfish.
• Among the $k$ clownfish Pak Chanek buys, the mean size of the female clownfish is equal to the mean size of the male clownfish.

Let $l$ and $r$ respectively be the minimum and maximum index of a clownfish Pak Chanek buys. What is the minimum possible value of $r-l$?

Input

The first line contains two integers $n$ and $k$ ($2 \leq k \leq n \leq 2\cdot10^5$) — the number of clownfish in the shop and the number of clownfish Pak Chanek has to buy.

The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1\leq a_i\leq n$) — the size of each clownfish.

Output

An integer representing the minimum possible value of $r-l$. If it is impossible to buy exactly $k$ clownfish and satisfy the problem's condition, print $-1$.

ExamplesInput

9 6
2 4 2 3 2 4 1 3 4

Output

6

Input

6 6
2 6 5 2 6 5

Output

-1

Input

5 4
1 2 3 4 5

Output

-1

Note

In the first example, Pak Chanek can do the following:

1. Do not buy clownfish $1$.
2. Buy clownfish $2$ and assign it as male.
3. Buy clownfish $3$ and assign it as female.
4. Buy clownfish $4$ and assign it as male.
5. Buy clownfish $5$ and assign it as male.
6. Do not buy clownfish $6$.
7. Buy clownfish $7$ and assign it as male.
8. Buy clownfish $8$ and assign it as female.
9. Do not buy clownfish $9$.

Then, we get that:

• The mean size among the $2$ female clownfish Pak Chanek buys is $\frac{2+3}{2} = 2.5$.
• The mean size among the $4$ male clownfish Pak Chanek buys is $\frac{4+3+2+1}{4} = 2.5$.
• $l=2$, $r=8$, $r-l=6$.

There are no better strategies.

题目大意：
Pak Chanek购买了一种他最喜欢的鱼类——小丑鱼，因为小丑鱼具有根据需要改变性别的独特能力。他的鱼缸大小决定了他需要购买恰好k条小丑鱼。在当地的鱼店，有n条编号从1到n的小丑鱼，每条小丑鱼都有一个大小a_i。最初，店里的小丑鱼都没有分配性别，但它们可以被分配为两种可能的性别：雌性或雄性。

店主有一个购买过程，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≤k≤n≤2×10^5）——鱼店中小丑鱼的数量和Pak Chanek需要购买的小丑鱼数量。
第二行包含n个整数a_1,a_2,a_3,…,a_n（1≤a_i≤n）——每条小丑鱼的大小。

输出数据格式：
一个整数，表示r-l的最小可能值。如果无法购买恰好k条小丑鱼并满足问题的条件，则输出-1。题目大意： Pak Chanek购买了一种他最喜欢的鱼类——小丑鱼，因为小丑鱼具有根据需要改变性别的独特能力。他的鱼缸大小决定了他需要购买恰好k条小丑鱼。在当地的鱼店，有n条编号从1到n的小丑鱼，每条小丑鱼都有一个大小a_i。最初，店里的小丑鱼都没有分配性别，但它们可以被分配为两种可能的性别：雌性或雄性。 店主有一个购买过程，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≤k≤n≤2×10^5）——鱼店中小丑鱼的数量和Pak Chanek需要购买的小丑鱼数量。 第二行包含n个整数a_1,a_2,a_3,…,a_n（1≤a_i≤n）——每条小丑鱼的大小。 输出数据格式： 一个整数，表示r-l的最小可能值。如果无法购买恰好k条小丑鱼并满足问题的条件，则输出-1。