Not Alone

A target array is nice iff there are no lonely equal-runs of length $1$.

More concretely, if you compress equal adjacent values into circular runs, then every run must have length at least $2$. That is the whole condition. No hidden graph nonsense, no weird global dependency. Just: every position must belong to some constant adjacent group of size at least $2$.

Cost of One Block

Suppose we decide that positions $l, l+1, \dots, r$ will all become the same value $x$. The cost is

$$\sum_{i=l}^{r} |a_i - x|.$$

This is minimized by choosing $x$ as a median of those values.

For this problem, we only need block sizes $2$ and $3$:

• For two values $u,v$, best cost is $|u-v|$.
• For three values $u,v,w$, best cost is

$$\max(u,v,w)-\min(u,v,w),$$

because the median is the middle value.

Why Blocks Larger Than 3 Are Useless

This is the key trick.

Take any constant block of length $k \ge 4$. You can split it into smaller consecutive blocks of lengths $2$ and $3$. This is always possible for every $k \ge 4$:

• $4 = 2+2$
• $5 = 2+3$
• bigger lengths keep peeling off $2$s or $3$s

Now let each smaller block choose its own best value. That can only decrease or preserve the cost, because choosing values independently is more flexible than forcing the entire big block to share one value.

And every smaller block still has length at least $2$, so every element still has an equal neighbor inside its own block. Nice condition satisfied. No drama.

Therefore, there is always an optimal answer where every block has length exactly $2$ or $3$.

So the problem is now:

Partition the circular array into consecutive groups of size $2$ or $3$, minimizing total median cost.

Linear DP

First ignore circularity. For a normal interval $[L,R]$, define $dp[i]$ as the minimum cost to cover the first $i$ elements of this interval.

Base:

$$dp[0]=0.$$

Transitions:

• If the last block has length $2$:

$$dp[i] = \min(dp[i], dp[i-2] + cost_2)$$

• If the last block has length $3$:

$$dp[i] = \min(dp[i], dp[i-3] + cost_3)$$

where

$$cost_2(x,y)=|a_x-a_y|$$

and

$$cost_3(x,y,z)=\max(a_x,a_y,a_z)-\min(a_x,a_y,a_z).$$

If the interval length is impossible to cover, like length $1$, the DP just returns infinity.

Handling the Circle

Cut the circle between positions $n$ and $1$.

In the optimal partition, either no block crosses this cut, or exactly one block crosses it. Since block sizes are only $2$ or $3$, the crossing block has only three possible shapes:

1. $(n,1)$
2. $(n-1,n,1)$
3. $(n,1,2)$

So try four cases:

1. No crossing block: solve the linear interval $[1,n]$.
2. Crossing pair $(n,1)$: pay its cost, then solve $[2,n-1]$.
3. Crossing triple $(n-1,n,1)$: pay its cost, then solve $[2,n-2]$.
4. Crossing triple $(n,1,2)$: pay its cost, then solve $[3,n-1]$.

Take the minimum.

That is it. The circle tries to look scary, but once blocks are capped at size $3$, it has only three ways to be annoying.

Correctness Proof

We prove the algorithm returns the minimum possible cost.

First, every nice array can be viewed as circular constant runs, each of length at least $2$. This follows directly from the definition: if a run had length $1$, that element would differ from both neighbors and would be alone.

Second, there exists an optimal nice array whose constant blocks all have length $2$ or $3$. Consider any block of length at least $4$. Split it into consecutive pieces of length $2$ and $3$. Each new piece has length at least $2$, so every element still has an equal neighbor inside its piece. Also, each new piece may choose its own median value, so the total cost cannot increase compared to forcing the original larger block to use one value. Repeating this removes all blocks of length at least $4$.

Thus, the original problem is equivalent to partitioning the circular array into consecutive blocks of length $2$ or $3$, with each block paid by its optimal median cost.

For a fixed linear interval, the DP is correct because the final block in any valid partition must have length $2$ or $3$. Removing that final block leaves an optimal partition of the previous prefix; otherwise we could improve the full solution. The recurrence checks both possible final block sizes, so it finds the optimal linear cost.

For the circular case, after cutting between $n$ and $1$, at most one block crosses the cut. Since every block has length $2$ or $3$, that crossing block must be exactly one of $(n,1)$, $(n-1,n,1)$, or $(n,1,2)$. If no block crosses, the whole circle is just one linear interval. The algorithm tries all four exhaustive cases and solves the remaining non-circular interval optimally with the DP.

Therefore, the minimum among those cases is exactly the optimal answer.

Complexity

Each linear DP is $O(n)$, and we run it only four times.

Total complexity per test case is:

$$O(n)$$

with $O(n)$ memory. Across all tests, this is easily fine for $\sum n \le 2\cdot 10^5$.