Friendly Gifts

Key observation: what does “good” really mean?

An array of length $L$ is good iff after rearranging it becomes

$$x, x+1, x+2, \dots, x+L-1.$$

So it must contain $L$ distinct values, and its range must have size $L$:

$$\max - \min + 1 = L.$$

Equivalently, every good segment is a permutation of some value block $[x, x+L-1]$.

What about the concatenation?

Suppose we choose two good arrays of length $L$.

Their value blocks are:

$$[x, x+L-1]$$

and

$$[y, y+L-1].$$

The concatenation has length $2L$ and must also be good, so its values must be exactly one consecutive block of length $2L$.

Two length-$L$ consecutive blocks can form such a block only if they are adjacent. So, after possibly swapping them:

$$y = x+L.$$

That means we only need to find two non-overlapping subsegments of length $L$ whose value blocks are:

$$[x,x+L-1] \quad\text{and}\quad [x+L,x+2L-1].$$

Enumerating all good subsegments

Since $\sum n \le 6000$, an $O(n^2)$ brute force is absolutely fine.

For every left endpoint $l$, extend the right endpoint $r$. Maintain:

• current minimum $mn$,
• current maximum $mx$,
• whether a value has already appeared.

If a duplicate appears, we can stop extending this $l$, because every longer segment still contains that duplicate and can never be good. Brutal, but correct.

For a segment $[l,r]$ with length

$$L = r-l+1,$$

it is good iff:

$$mx - mn + 1 = L.$$

When it is good, it represents the value block starting at $mn$. For each pair $(L,mn)$, store:

• $first[L][mn]$ = minimum starting position of such a segment,
• $last[L][mn]$ = maximum starting position of such a segment.

We only need min and max starts, not all occurrences. Nice little compression, no nonsense.

Checking non-overlap

Now fix a length $L$ and a value-block start $x$.

We need one occurrence of block $[x,x+L-1]$ and one occurrence of block $[x+L,x+2L-1]$.

Let their sets of starting positions be $A$ and $B$. Segments have length $L$, so starts $p$ and $q$ are non-overlapping iff:

$$|p-q| \ge L.$$

There exists an occurrence from $A$ before one from $B$ iff:

$$\min(A) + L \le \max(B).$$

Similarly, there exists one from $B$ before one from $A$ iff:

$$\min(B) + L \le \max(A).$$

So the condition is simply:

$$first_1 + L \le last_2 \quad\text{or}\quad first_2 + L \le last_1.$$

We scan $L$ from large to small and output the first valid one.

Complexity

Enumerating all good subsegments takes:

$$O(n^2)$$

Checking all possible adjacent value blocks also takes:

$$O(n^2).$$

Memory is:

$$O(n^2).$$

With $\sum n \le 6000$, this comfortably fits. The constraints are basically screaming “quadratic or bust”, and quadratic works.