Problem Description

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

or

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?

Input Format

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 Format

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.

5
1 1 1 1 2

2

Hint

Sample Explanation

One optimal plan is to change the $1$st and the $3$rd numbers to $2$. Then the sequence becomes:

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