P10840 [MX-J2-T1] Turtle and Sequences

Original link: .

You are given a sequence $a_1, a_2, \ldots, a_n$. You can perform some operations on this sequence. Suppose that before an operation, the sequence length is $m$. In this operation, you may choose an integer $i$ such that $1 \le i \le m - 1$ and $a_i \ne a_{i + 1}$, delete $a_{i + 1}$, and set the value of $a_i$ to **any integer**. Find the maximum number of operations you can perform.

The first line contains a positive integer $n$, indicating the initial length of the sequence. The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$.

Output a single non-negative integer in one line, indicating the maximum number of operations.

#### Sample Explanation #1 You can choose $i = 1$. After deleting $a_2$, set $a_1$ to $3$. Now $a = [3]$, and no more operations can be performed. Therefore, the answer is $1$. #### Sample Explanation #2 No operation can be performed, so the answer is $0$. #### Constraints **This problem uses bundled testdata and subtask dependencies are enabled.** | Subtask ID | Points | $n \le$ | Special Property | Subtask Dependencies | | :-: | :-: | :-: | :-: | :-: | | $1$ | $34$ | $2$ | None | None | | $2$ | $19$ | $10^5$ | $a_1 = a_2 = \cdots = a_n$ | None | | $3$ | $47$ | $10^5$ | None | $1, 2$ | For all testdata, $1 \le n \le 10^5$ and $1 \le a_i \le 10^9$. Translated by ChatGPT 5