Beautiful array

Many people mistakenly believe that Cossack Vus's favorite number is seven. In reality, his favorite number is two. Consequently, he only appreciates arrays that contain exactly two distinct numbers.

However, arrays with just two different numbers often appear chaotic to him, and Cossack Vus despises chaos. Therefore, he prefers arrays where every pair of adjacent elements are different.

Formally, for Vus to like an array, the following conditions must be satisfied:

• $a_i=a_{i+2}$ for all $i$ ($1\le i\le n-2$);

• $a_i\ne a_{i+1}$ for all $i$ ($1\le i\le n-1$).

For example, he likes the array $[1,4,1,4,1]$. This array contains only two different numbers, $1$ and $4$, and no two adjacent numbers are the same. However, he does not like the arrays $[1,4,5]$ (because there are three different numbers), $[1,1,1,1,1]$ (because there are identical adjacent elements and only one number), or $[7,7,6,6]$ (because there are identical adjacent elements).

Given an array $a$ with $n$ integers $a_1,a_2,\dots ,a_n$, you need to determine the minimum number of elements that must be changed for the array to be liked by Cossack Vus. Find this minimum number.

For instance, in the array $[1,1,1,1,1]$, you need to change the second and fourth elements to any other number. Therefore, in this example, the answer is $2$.

Input

The first line contains a single integer $n$ ($1\le n\le 10^5$) — the number of elements in the array.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the elements of the array.

Output

Output the minimum number of elements that need to be changed for the array to be liked by the Cossack.

Examples

Scoring

Solutions that work correctly under the constraints $n\le 100$ and $a_i\le 100$ will receive $40$ points.