Palindromex

Observation 1: the pair positions are everything

This problem looks like palindrome + mex, so your first instinct might be Manacher, hashes, black magic, or some other decorative nonsense. But the condition that every value appears exactly twice absolutely kills the problem.

Let $m=2n$ and use $1$-based indexing. For every position $i$, define $mate(i)$ as the position of the other occurrence of $a_i$.

Now take a palindromic subarray $[l,r]$ and set

$$S=l+r.$$

For every non-middle position $i \in [l,r]$, its mirrored position is $S-i$, so we must have

$$a_i=a_{S-i}.$$

But each value exists only twice in the whole array. So if $i$ is not the center of an odd-length palindrome, the other occurrence of $a_i$ is forced to be exactly $S-i$. Therefore

$$mate(i)=S-i \quad \Longleftrightarrow \quad i+mate(i)=S.$$

Define

$$b_i=i+mate(i).$$

Then in any palindrome with center-sum $S=l+r$, every non-center position inside it must satisfy

$$b_i=S.$$

That is the whole damn trick.

Observation 2: what does the maximal palindrome around a center look like?

For a fixed center, taking a larger palindrome cannot decrease mex. So for each center, we only care about the maximal palindrome around it.

Odd-length center at position $c$

Here $S=2c$. Position $c$ is the middle, so it is free: we do not require $b_c=2c$.

For every other included position $i$, we need

$$b_i=2c.$$

So the palindrome expands exactly while the positions immediately to the left of $c$ keep having value $2c$ in the array $b$.

If the longest consecutive block ending at $c-1$ with value $2c$ starts at $L$, then the maximal odd palindrome is

$$[L,\,2c-L].$$

If $c=1$ or $b_{c-1}\ne 2c$, then it is just $[c,c]$.

Why is the right end automatically $2c-L$? Because $b_i=2c$ means

$$mate(i)=2c-i,$$

so every left position forces its mirrored right position.

Also note that $b_c\ne 2c$ always, because $mate(c)\ne c$. So the equal-value block cannot pass through the center. Nice and clean.

Even-length center between $c$ and $c+1$

Now $S=2c+1$, and there is no free middle position. So every position in the palindrome must satisfy

$$b_i=2c+1.$$

Hence the maximal even palindrome is simply the maximal consecutive run of value $2c+1$ in $b$ that contains position $c$.

This run exists iff

$$b_c=2c+1.$$

So after building maximal equal-value runs of $b$, we can generate all candidate maximal palindromes in $O(m)$ total:

• one odd candidate for every $c \in [1,m]$,
• one even candidate for every gap $(c,c+1)$ that actually works.

So there are only $O(m)$ intervals to check.

Observation 3: reduce to offline range mex

Now we just need the mex of each candidate interval $[l,r]$.

This is a standard offline trick.

Sweep the array from left to right by right endpoint $r$. For every value $x$, maintain

$$last_x(r)=\text{the last position of }x\text{ in }[1,r].$$

Then $x$ appears in $[l,r]$ iff

$$last_x(r)\ge l.$$

Therefore

$$\operatorname{mex}(a_l,\dots,a_r)=\min\{x\mid last_x(r)<l\}.$$

So we keep all $last_x$ in a segment tree over the value axis $x\in[0,n]$:

• while sweeping, update $last_{a_r}=r$,
• for each query $[l,r]$, find the smallest $x$ with $last_x<l$.

We include a dummy value $n$ that never appears. So if $0,1,\dots,n-1$ are all present, the query naturally returns $n$.

This gives $O((m+q)\log n)$, where $q=O(m)$ is the number of candidate intervals.

How to build the candidate intervals in $O(m)$

Compute $b_i=i+mate(i)$.

Now build two helper arrays for the equal-value runs of $b$:

• $L_i$ = leftmost position in the run containing $i$,
• $R_i$ = rightmost position in the run containing $i$.

Both are easy in linear time.

Then:

Odd center $c$

• If $c=1$ or $b_{c-1}\ne 2c$, candidate is just $[c,c]$.
• Otherwise, let $l=L_{c-1}$. Then the maximal palindrome is

$$[l,\,2c-l].$$

Even center between $c$ and $c+1$

• If $b_c\ne 2c+1$, there is no even palindrome of length at least $2$ there.
• Otherwise, the maximal palindrome is exactly

$$[L_c,\,R_c].$$

That is it. No DP circus, no binary-search yoga, no suffering.

Why this is correct

Lemma 1

A subarray $[l,r]$ is a palindrome iff for every $i\in[l,r]$,

• either $i=\frac{l+r}{2}$ (the middle of an odd-length palindrome),
• or $mate(i)=l+r-i$.

Proof. The mirrored position of $i$ inside $[l,r]$ is $l+r-i$. Palindromicity means the values there are equal. Since every value has exactly two occurrences in the whole array, the second occurrence of $a_i$ is unique, so it must be exactly $l+r-i$. The converse is immediate. $\square$

Lemma 2

For a fixed center, the interval constructed above is exactly the maximal palindrome around that center.

Proof. By Lemma 1, all non-center positions must satisfy $b_i=S$, where $S$ is the center-sum. So the palindrome extends exactly through consecutive positions around the center where $b_i=S$, and it must stop at the first position where this fails. That is precisely how the interval is constructed. $\square$

Lemma 3

It is enough to consider only maximal palindromes around each center.

Proof. Any smaller palindrome with the same center is contained in the maximal one. Adding elements cannot remove existing values, so mex cannot decrease. $\square$

Lemma 4

The offline segment tree query returns the mex of every interval correctly.

Proof. After processing right endpoint $r$, $last_x(r)$ is the latest occurrence of $x$ in $[1,r]$. Thus $x$ appears in $[l,r]$ iff $last_x(r)\ge l$. So the smallest $x$ with $last_x(r)<l$ is exactly the mex. $\square$

By Lemmas $1$-$4$, we enumerate every relevant maximal palindrome, compute its mex correctly, and take the maximum. Done.

Complexity

Let $m=2n$.

• build $mate$ and $b$: $O(m)$
• build equal-value runs of $b$: $O(m)$
• generate all candidate intervals: $O(m)$
• answer all mex queries offline: $O(m\log n)$

So the total complexity per test case is

$$O(m\log n)=O(n\log n),$$

with $O(m)$ memory.