P16303 [Lanqiao Cup 2026 NOI Qualifier Java Group C] Xiaolan's Sequence

Xiaolan believes that a sequence is “good” if and only if it satisfies the following conditions: 1. Exactly two different integers appear in the sequence. 2. Any pair of adjacent elements are different. 3. For all valid indices $i$ ($1 \le i \le n - 2$), we have $a_i = a_{i+2}$. Equivalently, a good sequence must look like $$ x, y, x, y, x, y, \dots $$ or $$ y, x, y, x, y, x, \dots $$ where $x \ne y$, and only these two numbers appear in the entire sequence. Now Xiaolan has a sequence of length $n$. He can perform any number of modification operations. In each operation, he can change one element in the sequence to any positive integer. Xiaolan wants to know: what is the minimum number of elements that must be modified to turn the current sequence into a good sequence?

The input consists of two lines. The first line contains a positive integer $n$, representing the length of the sequence. The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$, representing Xiaolan's current sequence.

Output one line containing a non-negative integer $c$, representing the minimum number of elements that must be modified to make the sequence a good sequence.

### Sample Explanation One optimal plan is to change the $1$st and the $3$rd numbers to $2$. Then the sequence becomes: $$ 2, 1, 2, 1, 2 $$ This is a good sequence. It can be verified that there is no way to satisfy the conditions by modifying only $1$ element, so the answer is $2$. ### Constraints - For $30\%$ of the testdata, $n \le 8$. - Another $20\%$ of the testdata satisfy: for all $1 \le i, j \le n$, we have $a_i = a_j$. - For all testdata, $2 \le n \le 10^6$, and $1 \le a_i \le 10^6$. Translated by ChatGPT 5