서로 다른 구간 지우기

Suppose a value $x$ appears $M$ times in the sequence. Since every deleted segment must have pairwise distinct elements, one operation cannot delete two or more occurrences of $x$.

Therefore, to delete one occurrence of $x$, the same operation must also delete at least one element different from $x$. There are only $N-M$ elements different from $x$, so at most $N-M$ occurrences of $x$ can be deleted. Hence at least

$$M-(N-M)=2M-N$$

occurrences of $x$ must remain.

Taking the maximum over all values, if $M$ is the maximum frequency of any value, the answer is at least

$$\max(0,2M-N).$$

We now show that this lower bound is always achievable.

First, suppose $M>N/2$. Let $x$ be a most frequent value. As long as there is an element different from $x$, there must be an adjacent pair consisting of one $x$ and one non-$x$ element. These two elements are distinct, so we can delete this segment of length $2$. Repeating this removes all non-$x$ elements and the same number of $x$ elements. Thus exactly $2M-N$ elements remain.

Now suppose $M \le N/2$. We claim that all elements can be deleted. This can be proved by induction on the current length of the sequence.

Let the current length be $n$ and let $M$ be the current maximum frequency.

• If $n=2$, the two elements must be distinct, so they can be deleted at once.
• If the maximum frequency is small enough, deleting any adjacent unequal pair keeps every frequency at most half of the new length, so the induction hypothesis applies.
• If a value has frequency close to half, there is a boundary where that value is adjacent to a different value. Deleting this pair decreases the critical frequency.
• The only delicate case is when $n$ is odd and two different values each appear $(n-1)/2$ times. If those two values are adjacent, delete that adjacent pair. Otherwise, the single remaining value lies between them somewhere, so there is a segment of length $3$ containing three pairwise distinct values. Delete that segment. In both cases, the induction hypothesis applies afterward.

Therefore, when $M \le N/2$, the whole sequence can be deleted.

Hence the answer is

$$\max(0,2M-N),$$

where $M$ is the maximum frequency of any value.

The implementation only needs to count frequencies and find the maximum one.

The time complexity is $O(N)$.