Observations

For simplicity, let's denote ~[L, R]~ as the subarray ~[p_L, p_{L+1},...,p_{R}]~.

Observe that ~f(x)~ is monotonic, that is ~f(x) \geq f(x+1)~. The proof is not difficult to see, as any valid pair ~(l, r)~ that satisfies ~\operatorname{mex}([l, r])-\operatorname{med}([l, r]) \geq x+1~ will also satisfy ~\operatorname{mex}([l, r])-\operatorname{med}([l, r]) \geq x~, therefore ~f(x)~ will always be at least ~f(x+1)~.

From this, we can binary search the maximum ~x~ such that ~f(x) \geq K~. The rest of the editorial will explain computing ~f(x)~ for ~1 \leq x \leq N~. We do not need to consider when ~x = 0~ because ~f(0) = f(1)~ (the ~\operatorname{mex}~ of a subarray will never equal to the ~\operatorname{med}~).

Computing ~f(x)~

We can iterate an integer ~m~ from ~1 ...N~ and count the number of pairs ~(l, r)~ such that ~\operatorname{mex}([l, r]) = m~ and ~m - \operatorname{med}([l, r]) \geq x~.

Let ~\operatorname{pos}[x]~ be the index of the value ~x~ in the permutation ~p~, ~L_m = \min_{i=0}^{m-1} \operatorname{pos}[i]~, and ~R_m = \max_{i=0}^{m-1} \operatorname{pos}[i]~. This means that ~[L_m, R_m]~ is the smallest subarray that contains all the integers ~0 ...m-1~. There are two restrictions that must be satisfied for a pair ~(l, r)~ to have a ~\operatorname{mex}([l, r]) = m~.

• The subarray must contain all integers from ~0~ to ~m-1~. This means that ~l \leq L_m~ and ~R_m \leq r~.
• The subarray must not contain ~m~, meaning that either ~\operatorname{pos}[m] < l~ or ~r < \operatorname{pos}[m]~.

Next, ~m - \operatorname{med}([l, r]) \geq x~, which can be rewritten as ~\operatorname{med}([l, r]) \leq m - x~. Notice that if the subarray contains all integers ~0 ...m-1~, then there are exactly ~m-x+1~ integers in the subarray that are ~\leq m-x~ (assuming ~m-x \geq 0~). This means that the subarray can include at most ~m-x+1~ extra integers to make the median ~\leq m - x~. Therefore, the subarray can have a length of at most ~2 \cdot (m-x + 1)~, meaning that a pair ~(l, r)~ must satisfy ~r - l + 1 \leq 2 \cdot (m - x + 1)~.

Now let's see how we can use the above restrictions to count the number of pairs for each ~m~. There are two cases we need to consider:

Case 1: ~\operatorname{pos}[m] < L_m~

• ~l~ can be chosen from the range ~[\operatorname{pos}[m] + 1, L_m]~ and ~r~ must satisfy ~R_m \leq r \leq N~ and ~r - l + 1 \leq 2 \cdot(m - x + 1)~. We can iterate every ~l~ from ~[\operatorname{pos}[m] + 1, L_m]~ and add ~\max(0, \min(N, l+2\cdot(m-x+1)-1) - R_m+1)~ to the number of pairs.

Case 2: ~\operatorname{pos}[m] > R_m~

• ~r~ can be chosen from the range ~[R_m, \operatorname{pos}[m]-1]~ and ~l~ must satisfy ~1 \leq l \leq L_m~ and ~r-l+1 \leq 2 \cdot (m-x+1)~. We can iterate every ~r~ from ~[R_m, \operatorname{pos}[m]-1]~ and add ~\max(0, L_m - \max(1, r-2\cdot(m-x+1)+1)+1)~ to the number of pairs.

Note that when ~m = N~, although ~N~ does not exist in the permutation, we can let ~\operatorname{pos}[N] = 0~ and still run the above algorithm.

Time Complexity: While there are nested loops (iterating ~l~ or ~r~ inside the ~m~ loop), notice that ~L_m~ strictly decreases and ~R_m~ strictly increases as ~m~ grows. We only iterate over new indices, meaning that no index is visited more than once across the entire execution of ~f(x)~. Thus, ~f(x)~ runs in amortized ~\mathcal{O}(N)~ time.

Final Solution

The final solution consists of binary searching for the largest ~x~ in the range ~1 ...N~ such that ~f(x) \geq K~. If no such ~x~ exists, then the answer is ~-1~.

~f(x)~ can be computed in ~\mathcal{O}(N)~, so the final time complexity of the solution is ~\mathcal{O}(N\log N)~.

Bonus: Try to find a way to count the number of pairs for each ~m~ in ~\mathcal{O}(1)~ without iterating ~l~ or ~r~.