Diadrash (Easy Version)

We are given the hidden permutation directly in the hacked version, so this becomes a clean offline interval problem.

The obvious move is to compute the MEX of every query range. That works conceptually, but it is way too chunky if you do it from scratch: $q$ can be huge. Instead, flip the question around.

A range has MEX at least $x$ iff it contains all values

$0,1,2,\dots,x-1.$

Because $p$ is a permutation, every value has one position. Let $pos[v]$ be the index where value $v$ appears.

For a fixed $x$, the range must contain every position

$pos[0], pos[1], \dots, pos[x-1].$

That is equivalent to containing just their span:

$L_x = \min_{0 \le v < x} pos[v], \qquad R_x = \max_{0 \le v < x} pos[v].$

So a query range $[l,r]$ has MEX at least $x$ iff

$l \le L_x \quad \text{and} \quad R_x \le r.$

That is the whole trick. No need to inspect actual range contents. The values already told us their positions. Very polite of them.

From Exact MEX To A Threshold

The answer asks for the maximum exact MEX among the given ranges. But we can instead maximize the threshold condition “MEX is at least $x$”.

If some range has MEX $m$, then it has MEX at least every $x \le m$. Conversely, if some range has MEX at least $x$, then the maximum MEX is at least $x$.

Therefore the answer is:

$\max x \text{ such that some given range contains } [L_x,R_x].$

For $x=0$, this is always true, because every range has MEX at least $0$. So initialize the answer to $0$.

For $x \ge 1$, we scan values in increasing order and maintain the span:

• after adding value $x-1$, update $L = \min(L, pos[x-1]), \qquad R = \max(R, pos[x-1]);$
• check if some input range contains $[L,R]$;
• if yes, answer can be at least $x$.

Checking Containment Fast

Now we need to answer this repeatedly:

Given a segment $[L,R]$, does there exist a query range $[l,r]$ with

$l \le L \quad \text{and} \quad r \ge R?$

For every left boundary $i$, store the best right endpoint of any range starting exactly at $i$:

$startBest[i] = \max r \text{ among ranges } [i,r].$

Then prefix-max it:

$bestLeft[i] = \max(bestLeft[i-1], startBest[i]).$

Now $bestLeft[i]$ means:

among all query ranges with left endpoint at most $i$, what is the farthest right endpoint?

So a segment $[L,R]$ is contained in some query range iff

$bestLeft[L] \ge R.$

That is an $O(1)$ check.

Algorithm

For each test case:

1. Read $n,q$ and the permutation.
2. Build $pos[value]$.
3. Read all query ranges and build startBest[l] = max(startBest[l], r).
4. Prefix-max startBest so startBest[i] becomes the maximum right endpoint among ranges with left endpoint $\le i$.
5. Set ans = 0.
6. Scan values $0$ through $n-1$:
   • update the current span $[L,R]$ using pos[value];
   • if startBest[L] >= R, then some range has MEX at least value + 1, so update ans.
7. Print ans.

Why This Is Correct

We prove the algorithm returns the maximum MEX among all given ranges.

First, for any integer $x \ge 1$, a range has MEX at least $x$ iff it contains every value from $0$ to $x-1$. Since $p$ is a permutation, those values appear at positions $pos[0],\dots,pos[x-1]$. A range contains all those positions iff it contains their minimum and maximum position span $[L_x,R_x]$. Thus a query range has MEX at least $x$ iff it contains $[L_x,R_x]$.

Second, after prefix-maxing, startBest[L] is the largest right endpoint among all query ranges whose left endpoint is at most $L$. Therefore startBest[L] >= R holds iff there exists a query range $[l,r]$ with $l \le L$ and $r \ge R$, which is exactly the condition that the query range contains $[L,R]$.

The scan considers every possible threshold $x=1..n$, maintaining exactly $[L_x,R_x]`. It marks$x$achievable precisely when some query range has MEX at least$x$. Since the maximum exact MEX equals the largest achievable threshold, the final answer is correct.

Complexity

Building positions takes $O(n)$. Reading ranges and building prefix maxima takes $O(n+q)$. Scanning all possible MEX thresholds takes $O(n)$.

So each test case runs in

$O(n+q)$

with $O(n)$ memory. That easily fits. No drama, no segment tree cosplay needed.