Beautiful Problem

For a fixed $x$, every value belongs to one of three groups:

• small: values $<x$;
• neutral: values $=x$;
• large: values $>x$.

An interval fails exactly when it contains at least one small and at least one large. Neutral values are just filler; they do not matter.

So for this $x$, define

$L=\#\{a_i<x\},\qquad G=\#\{a_i>x\}.$

The question becomes:

Can we choose $L$ positions for small values and $G$ positions for large values so that no given interval contains both types?

If yes, the equal values fill the remaining positions. Clean.

Reduce the constraints to color switches

Imagine deleting all neutral positions. We are left with a subsequence of colored positions, each either small or large.

If some interval contains both colors, then among the colored positions inside that interval there must be two neighboring colored positions with different colors. So instead of checking all pairs of opposite colors, we only need to know when we are allowed to switch color between two consecutive colored positions.

For each position $i$, compute

$b_i=\min l$

among all intervals $[l,r]$ with $l\le i\le r$. If no interval covers $i$, set $b_i=i$.

Now suppose the previous colored position is $p<i$, and we want to color position $i$ with the opposite color.

• If $p\ge b_i$, then the interval that gives $b_i$ covers both $p$ and $i$, so switching color is illegal.
• If $p<b_i$, then no interval can cover both $p$ and $i$. If one did, its left endpoint would be at most $p$, contradicting the minimality of $b_i$.

Therefore:

$\text{opposite-color transition into } i \text{ is legal iff } p<b_i.$

Same-color transitions are always fine, because an interval containing two smalls or two larges is not a problem.

DP

Use 0 for small and 1 for large.

Let

$dp[i][s][c]$

be the maximum number of large positions we can place if:

• position $i$ is colored;
• its color is $c$;
• exactly $s$ small positions have been placed.

We also maintain prefix maxima:

$pref[i][s][c]=\max_{0\le j\le i} dp[j][s][c].$

This lets us choose the previous colored position quickly.

When coloring position $i$ with color $c$:

• if the previous colored position has the same color, it can be anywhere before $i$;
• if it has the opposite color, it must be before $b_i$.

Let

$ps=s-[c=0].$

That is the number of small positions used before coloring $i$.

Transitions:

$dp[i][s][c]\leftarrow pref[i-1][ps][c]+[c=1]$

for continuing the same color, and

$dp[i][s][c]\leftarrow pref[b_i-1][ps][1-c]+[c=1]$

for switching colors.

The fake state at position $0$ initializes both colors with zero placed elements, so the first real colored position can be either color. Slightly hacky, but it saves annoying casework.

After processing all positions, the maximum number of large positions possible with exactly $L$ small positions is

$\max(pref[n][L][0],pref[n][L][1]).$

So $x$ is valid iff this value is at least $G$. If we can place more than $G$ large positions, just turn the extras into neutral positions. Removing colored positions cannot create a bad interval, because deletion never creates a new opposite-colored pair. No magic, no weird vibes.

Correctness proof

Lemma 1. For a fixed $x$, an interval is invalid iff it contains at least one value $<x$ and at least one value $>x$.

Proof. The interval is invalid exactly when

$\min < x < \max.$

That is exactly the condition that some value is below $x$ and some value is above $x$. Values equal to $x$ do not change this. QED.

Lemma 2. For a fixed $x$, feasibility depends only on $L=\#\{a_i<x\}$ and $G=\#\{a_i>x\}$.

Proof. By Lemma 1, only the positions of values below and above $x$ matter. All values equal to $x$ are neutral filler. QED.

Lemma 3. Let $p<i$ be consecutive colored positions after deleting neutral positions, and suppose their colors differ. This transition is legal iff $p<b_i$.

Proof. If $p\ge b_i$, take an interval covering $i$ whose left endpoint is $b_i$. Since intervals are contiguous, it also contains $p$, so it would contain both colors. Illegal.

If $p<b_i$, then no interval covers both $p$ and $i$. Otherwise that interval would cover $i$ and have left endpoint at most $p$, which is smaller than $b_i$. Contradiction. QED.

Lemma 4. A coloring is valid iff every pair of consecutive colored positions with different colors satisfies the rule from Lemma 3.

Proof. If such a consecutive pair violates Lemma 3, some interval contains both colors, so the coloring is invalid.

Conversely, suppose a coloring is invalid. Then some interval contains both colors. Look at the colored positions inside that interval in increasing order. Somewhere in that list the color changes, giving two consecutive colored positions of different colors inside the same interval. By Lemma 3, that switch violates the rule. QED.

Lemma 5. The DP computes exactly the maximum number of large positions obtainable for every number of small positions and ending color.

Proof. Consider the last colored position $i$ and its color $c$. If the previous colored position has color $c$, it can be any earlier colored position, represented by $pref[i-1][ps][c]$. If it has color $1-c$, Lemma 3 says it must be before $b_i$, represented by $pref[b_i-1][ps][1-c]$. These are exactly all legal possibilities for the previous colored position, and the transition adds the contribution of position $i$. Induction over $i$ proves the claim. QED.

Theorem. The algorithm outputs 1 for exactly those values $x$ for which a valid rearrangement exists.

Proof. For value $x$, Lemmas 1 and 2 reduce the problem to placing exactly $L$ small and $G$ large positions. By Lemmas 4 and 5, the DP tells us the largest number of large positions possible while using exactly $L$ small positions. If it is at least $G$, we keep $G$ of those large positions and make the rest neutral. If it is less than $G$, no valid placement has enough large positions. Therefore the check is necessary and sufficient. QED.

Complexity

Computing all $b_i$ takes $O(nm)$ by directly applying each interval to its covered positions. This is fine because the input guarantees bound the total $n^2$ and $m^2$, so total $nm$ is also bounded.

The DP has $O(n^2)$ states and $O(1)$ transitions per state.

Overall per test case:

$O(nm+n^2)$

with $O(n^2)$ memory.