To solve this problem first we need to do some observations:

let's denote**l_k** = no. of elements *less* than **k**,**g_k** = no. of elements *greater* than **k**,**e_k** = no. of elements *equal* to **k**.

**(1)** let us first state, "when there is no solution for this problem":

if **l_k >= e_k + g_k** for all possible *subarray* where each *subarray length* is *greater than* **1**, then its not possible to have a solution for this problem, cause **k** would never be able to be the median of the subarray.

**(2)** if we can't construct a solution for any of the subarrays of length **w**, then there would be no solution of any subarray of length **w+1**. And if there is a solution for **w**(where *w > 1*), then it is also possible to construct a solution for **w+1** no matter what the consecutive elements are. [note: this is the most important observation]

**(3)** the elements can be represented as only two types **a[i] < k** and **a[i] >= k**. So, if we turn them into **+(positive transition)** and **-(negative transition)** operation then, there would be only two types of transitions. And we can easily represent them in diagrams like below:

```
// _ _ _
// (i) _| |_| |_| |_...
//
// or
//
// (ii) _
// |_ _
// |_ _| |_...
// |_|
//
// or
// _
// _| |_
// _| |_...
// _|
// (iii) _|
//
// etc...
```

The graph shows us one thing clearly, "when it is possible to make **e_k + g_k > l_k**":**e_k + g_k > l_k** is possible if the graph contains any of the following segment for once:

```
// _ _
// (i) | |_| | : +, -, +
//
// _
// _|
// (ii) _| : +, +, any type of transitions
//
//
// _
// (iii) _| : -, + , +
// |_|
//
```

In summary it shows that if there are *at least two positive transitions between three consecutive transitions*, then it is possible to fill the array with **k** if there is *at least one k* present in the array.

**(4)** Let's denote *positive transitions* as **+1** and *negative transitions* as **0**, then in each subarray of **size 3** if there is *at least one subarray* that confirms *two positive transitions(considering k is present at least once in the array)*, we would be able to fill the array. Example of such subarray(for transitions) would be like: (1, 0, 1) or (1, 1, 0) or (0, 1, 1) or (1, 1, 1) etc...

**Solution:**

```
let flag = false, seenK = false;
let np = 0; // counts no. of positive transitions in subarray size of 3
for i = 0...n-1:
seenK |= (a[i] == k) // check if we've been seen k at least once in the array
np += ((a[i] >= k) ? 1 : 0);
if i >= 3:
np -= ((a[i-3] >= k) ? 1 : 0);
if np >= 2:
flag = true;
if seenK and (flag || (n == 1 && np == 1)/*check for exceptional case when n == 1*/):
print "yes"
else:
print "no"
```

The solution link is given here.

Hey thanks for making such a great editorial. Can you also mention how to prove the second point?(If there is a solution for length l, there is a solution for length l+1).

Consider the subarray

`{3, 1, 4, 4}`

. It has no immediate solution for length $$$2$$$, but does for length $$$3$$$. Once you make the changes for this, you can proceed to get valid subarrays of length $$$4, 5, 6, ...$$$ At least that's what I think he meant to say.let's say there's a solution for subarray of length

l(l > 1).let's consider this subarray of length l as

a[i...j](where, j-i+1 = l)now, if

a[i...j]have asolution, then we canchange all the elements of a[i..j] to ki.e.

a[i] = a[i+1] = a[i+2] = .... = a[j] = know, consider all the possible values for a[i-1] and a[j+1]

there's four possibilities where a[i-1] and a[j+1] none of them are k(let's say i-1>=1 and j+1<=n, n means length of a):

(i) a[i-1....j+1] = [k+x, k, k, ...., k+y] (where, x > 0 && y > 0)

(ii) a[i-1....j+1] = [k-x, k, k, ...., k-y] (where, x > 0 && y > 0)

(iii) a[i-1....j+1] = [k+x, k, k, ...., k-y] (where, x > 0 && y > 0)

(iv) a[i-1....j+1] = [k-x, k, k, ...., k+y] (where, x > 0 && y > 0)

I hope you get the scenario.

Part-01: for a[i....j+1]Now, let's consider the subarray

a[i....j+1], can you construct a solution?(remember l>1)let's try to find the median, which is

(((j+1)-(i)+1) / 2) = (h / 2) th element[note: j-i+1 = l, and so, h = l + 1]for

h == 3(a[i, j, j+1]), median would be2nd element, which isk(whatever, a[j+1] holds, cause, after sort the possible sequence would be (k, k, k+x) or (k-x, k, k) and 2nd element would always be k)for

h == 4(a[i, j-1, j, j+1]), median would be2nd element, which isk(whatever a[j+1] holds)...

...

so on...

so no matter what a[j+1] holds the median always would be some index which holds k

Part-02: for a[i-1...j]You can just apply the rules as I have done in part-01 and prove it yourself.

I hope this helps you.

Thanks a lot!