Make a Palindrome

Let $x$ be the $k$-th smallest value of the original array.

This value is the entire problem. Everything else is noise wearing a fake mustache.

What can never be deleted?

Any value smaller than $x$ is impossible to delete.

Why? Suppose $a_i < x$. In the whole array, there are fewer than $k$ elements with value at most $a_i$, because $x$ is the $k$-th smallest. Any subarray has no more such elements than the whole array. So inside any valid chosen segment, $a_i$ cannot be the $k$-th smallest. It is too small. It is stuck forever.

So every element $<x$ must appear in the final palindrome, in the same relative order.

What about values bigger than $x$?

They do not need to survive. In the intended final array, we can delete all of them. They are not part of the hard core.

The only delicate value is exactly $x$. Some copies of $x$ can be deleted, but not all of them.

Let

$c = \#\{i : a_i < x\}.$

Since $x$ is the $k$-th smallest, $c < k$. Once the current array has fewer than $k$ elements, no operation is possible. Also, the undeletable elements $<x$ always remain. Therefore the final array must contain at least $k-1$ elements whose values are at most $x$; otherwise we would have deleted too many copies of $x$.

So the number of copies of $x$ that must remain is

$need = k - 1 - c.$

This is always nonnegative.

Now ignore every value $>x$. Those can be deleted. Consider the filtered sequence

$b = [a_i \mid a_i \le x].$

In this sequence:

• every value $<x$ is mandatory,
• every value $=x$ is optional,
• but at least $need$ copies of $x$ must be kept.

So the problem becomes:

Can we delete at most

$\#\{i : a_i=x\} - need$

copies of $x$ from $b$ so that $b$ becomes a palindrome?

That is now just a two-pointer problem.

Put pointers $l$ and $r$ at the ends of $b$.

• If $b_l=b_r$, keep both and move inward.
• If $b_l\ne b_r$, then at least one side must be deleted.
• But only values equal to $x$ are deletable inside $b$.

So:

• if $b_l=x$, delete/skip the left side;
• else if $b_r=x$, delete/skip the right side;
• else both are mandatory smaller values and they mismatch, so the answer is NO.

Count how many $x$'s you skip. If the number skipped is at most the allowed amount, answer YES.

There is one tiny center case: when $l=r$, one element remains in the middle, which is always fine for palindrome purposes. If that middle element is $x$, we keep it, not skip it. No drama.

Why this is sufficient

The two-pointer procedure constructs a palindromic subsequence of $b$ containing all mandatory values $<x$ and enough copies of $x$. All values $>x$ are discarded, and the skipped copies of $x$ are also discarded.

Those deletions are achievable because we never try to delete a value smaller than $x$, and we leave at least $k-1$ elements with value at most $x$ alive. Values greater than $x$ and the extra copies of $x$ can be removed in some order while the required small core remains. The operation’s annoying wording basically enforces exactly this threshold behavior.

So the whole solution is:

1. Find the $k$-th smallest value $x$.
2. Build $b$ from all elements $\le x$.
3. Compute how many copies of $x$ may be removed.
4. Run the greedy two-pointer check.

Sorting costs $O(n\log n)$ per test case, and the two-pointer scan is linear. With total $n\le 2\cdot 10^5$, this is comfortably AC.