Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

graphs

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Indefinite Clownfish

time limit per test

3.5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputPak 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$$$.

Examples

Input

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:

- Do not buy clownfish $$$1$$$.
- Buy clownfish $$$2$$$ and assign it as male.
- Buy clownfish $$$3$$$ and assign it as female.
- Buy clownfish $$$4$$$ and assign it as male.
- Buy clownfish $$$5$$$ and assign it as male.
- Do not buy clownfish $$$6$$$.
- Buy clownfish $$$7$$$ and assign it as male.
- Buy clownfish $$$8$$$ and assign it as female.
- 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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 10:12:07 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|