Beautiful Palindromes

The goal is to minimize the number of palindromic subarrays after appending $k$ values.

Some palindromes are completely out of our control:

• every palindrome already inside the original array stays there,
• every appended element is a length-$1$ palindrome by itself.

So the absolute best possible result is: create exactly $k$ new palindromes, one singleton for each appended value, and create no longer palindrome. If we manage that, we are done. No need to count anything.

What changes when we append one value?

When we append a new value, the only newly created subarrays are the ones ending at this new last position. Everything else already existed before.

So we want every appended position to be “safe”: no palindromic subarray of length at least $2$ should end there.

The useful transition

Suppose the current last position is already safe. Now append a value $v$.

If a new palindrome ending at $v$ has length $2$, then $v$ equals the previous value.

If it has length $3$, then $v$ equals the value two positions before it.

If it has length at least $4$, strip off the two equal outer values. The inside is still a palindrome, has length at least $2$, and ends at the previous position. But the previous position was safe, so that cannot happen.

Therefore, after we already have one safe appended position, the rule is simple:

$$v \ne \text{last value}, \qquad v \ne \text{second last value}.$$

That is the whole engine of the solution.

The annoying part is only the first append. The original array may already have palindromic suffixes, so blindly avoiding the last two values can fail. Example:

$$[1,2,2] + 1 = [1,2,2,1]$$

That creates a length-$4$ palindrome. So yeah, the naive greedy gets folded instantly.

How to make the first append safe

There are two cases.

Case 1: some value is missing from the original array

Let $x$ be a number in $[1,n]$ that does not appear in $a$.

Appending $x$ is immediately safe: any non-singleton palindrome ending at this new $x$ would need another $x$ as its left endpoint, but no such $x$ exists in the original array.

Now choose:

• $z = a_n$, the last original value,
• $y$ as any value different from both $x$ and $z$.

This is always possible because $n \ge 3$.

Then append cyclically:

$$x, y, z, x, y, z, \dots$$

Check the first few steps:

• $x$ is safe because it was missing from the original array.
• $y$ differs from both $x$ and $a_n$.
• $z$ differs from both $x$ and $y$.
• after that, every next value in the $x,y,z$ cycle differs from the previous two.

By the transition above, every appended position is safe.

Case 2: no value is missing

Then the array is a permutation of $1,2,\dots,n$.

Use the last three original values:

$$x = a_{n-2}, \qquad y = a_{n-1}, \qquad z = a_n.$$

They are distinct because the array is a permutation.

Appending $x$ first is safe. Why? The only previous occurrence of $x$ is at position $n-2$. The possible long palindrome would have to use:

$$[a_{n-2}, a_{n-1}, a_n, x]$$

but this is not a palindrome because $a_{n-1} \ne a_n$. There is no earlier occurrence of $x$, so no other start is possible.

Then append cyclically again:

$$x, y, z, x, y, z, \dots$$

After the first safe append, the same “different from the previous two” argument keeps everything safe.

Why this is optimal

Every appended value must create one singleton palindrome. That means at least $k$ new palindromic subarrays are unavoidable.

The construction above creates exactly those $k$ singleton palindromes and no non-singleton palindrome ending at any appended position.

So it reaches the lower bound. That is optimal. The problem tries to look like counting; it is actually just a clean construction.

Algorithm

For each test case:

1. Count which values from $1$ to $n$ appear in $a$.
2. If there is a missing value $x$:
   • set $z=a_n$,
   • choose any $y$ with $y \ne x$ and $y \ne z$,
   • use pattern $[x,y,z]$.
3. Otherwise:
   • use pattern $[a_{n-2},a_{n-1},a_n]$.
4. Print the first $k$ values of this repeating pattern.

Complexity

Counting appearances costs $O(n)$ per test case, and printing costs $O(k)$.

So the total complexity is:

$$O(n+k)$$

which is easily fine because $\sum n \le 2\cdot 10^5$ and $k \le n$.