Indefinite Clownfish
Contest: Codeforces Round 902 (Div. 1, based on COMPFEST 15 - Final Round)
Difficulty rating: 3500
Tags: binary search, graphs

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 format:
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 format:
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$$$.

Constraints:
Time limit: 3.5 s
Memory limit: 512.0 MB

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.

Example input:
9 6
2 4 2 3 2 4 1 3 4

Example output:
6

Example input:
6 6
2 6 5 2 6 5

Example output:
-1

Editorial:
We want to find two disjoint subsequences (for the females and the males) such that:
• The female subsequence contains consecutively increasing values.
• The male subsequence contains consecutively decreasing values
• The total length is exactly $$$k$$$.
• The mean values of both subsequences are the same.
For a group of consecutive values with minimum value $$$\text{min}$$$ and maximum value $$$\text{max}$$$, the mean is $$$\frac{\text{max}+\text{min}}{2}$$$. So we must make both values of $$$\text{max}+\text{min}$$$ the same.
We can obtain that since both means are equal, the two subsequences must contain at least one common value. And a common value can only occur twice in the entirety of the two subsequences.
For a way to choose the two subsequences, let $$$x$$$ be a common value of the two subsequences such that the difference in indices of its two occurences is minimum. Let $$$p$$$ and $$$q$$$ be the indices of the left and right occurences of $$$x$$$ respectively. There are two cases, either the $$$p$$$ is female and $$$q$$$ is male, or vice versa. If the $$$p$$$ is female, the following must be true:
• To the left $$$p$$$, in decreasing indices, the chosen subsequence (the female one) has the values $$$x-1$$$, $$$x-2$$$, $$$x-3$$$, and so on.
• To the right of $$$q$$$, in increasing indices, the chosen subsequence (the male one) has the values $$$x-1$$$, $$$x-2$$$, $$$x-3$$$, and so on.
How about the values in the chosen subsequences that are bigger than $$$x$$$? Would they conflict in the indices between $$$p$$$ and $$$q$$$? Well, since we choose $$$x$$$ with the minimum difference in indices of its two occurences, then all values bigger than $$$x$$$ in the chosen subsequences that are located between $$$p$$$ and $$$q$$$ are either only from the female subsequence or only from the male subsequence. So, we only need to consider where for a fixed index that is either $$$p$$$ or $$$q$$$:
• To the left of that index, in decreasing indices, the chosen subsequence (the male one) has the values $$$x+1$$$, $$$x+2$$$, $$$x+3$$$, and so on.
• To the right of that index, in increasing indices, the chosen subsequence (the female one) has the values $$$x+1$$$, $$$x+2$$$, $$$x+3$$$, and so on.
That means, if $$$p$$$ is female, there are two cases (either choosing the index to be $$$p$$$ or $$$q$$$). If $$$p$$$ is male, a similar thing also applies, but the roles of the values smaller than $$$x$$$ and the values bigger than $$$x$$$ are switched, so there are also two cases. So there are only four cases in total.
Notice that in each of the four cases, we can see it as having a pair of indices $$$(p, q)$$$ with the same value and having four legs of consecutive values coming out of it in four different directions. Notice that the elements in different legs can never conflict with each other. Each leg is independent.
Let's group the four legs into two groups, the two left legs and the two right legs. Next, define $$$\text{min}_f$$$ and $$$\text{max}_f$$$ as the minimum and maximum value in the female subsequence and define $$$\text{min}_m$$$ and $$$\text{max}_m$$$ as the minimum and maximum value in the male subsequence. It must hold that $$$\text{max}_f+\text{min}_f=\text{max}_m+\text{min}_m$$$. So $$$\text{max}_m-\text{min}_f=\text{max}_f-\text{min}_m$$$.
Notice that $$$\text{max}_m-\text{min}_f$$$ is the total number of elements in the two left legs and $$$\text{max}_f-\text{min}_m$$$ is the total number of elements in the two right legs if we exclude $$$p$$$ and $$$q$$$. Since we want to make the number of elements in the two groups the same, each group must contain exactly $$$\frac{k-2}{2}$$$ elements. This means if $$$k$$$ is odd, it is impossible.
We obtain that we can handle the two groups independently. We just need to make sure the number of elements in one group is exactly $$$\frac{k-2}{2}$$$. We want to minimise the value of $$$r-l$$$. This means, we want to maximise $$$l$$$ in the left group and minimise $$$r$$$ in the right group. These two tasks are equivalent, just mirrored.
To solve this, let's construct a graph using the array. Each element $$$a_i$$$ in the array has four parents:
• The rightmost element to the left of it with value $$$a_i-1$$$.
• The rightmost element to the left of it with value $$$a_i+1$$$.
• The leftmost element to the right of it with value $$$a_i-1$$$.
• The leftmost element to the right of it with value $$$a_i+1$$$.
For each type of parent, construct the binary lifting for it so that for each element, we can get its $$$d$$$-th parent of a certain for any value of $$$d$$$ in $$$O(\log n)$$$.
Using this, in order to calculate the maximum value of $$$l$$$ of the left group, we can do a binary search to find the optimal number of elements in each of the two left legs. We do the same thing for the right group. We do this for each of the four cases to finally find the minimum value of $$$r-l$$$ for a particular pair of $$$(p, q)$$$.
We do that entire process repeatedly for all pairs of adjacent occurences of the same value.
Time complexity: $$$O(n\log^2n)$$$