Sakurako and a Christmas Array

Sakurako has recently decorated an array in a way that it became a Christmas array. It was glorious, until Chefir came and messed it up.

An array of length $n$ is called glorious if the following holds:

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

• and there is an element which occurs more than $\frac{n}{2}$ times.

You are given an array $a$ of length $n$, where $n$ is even. You are asked what is the minimum amount of elements that you need to replace in order for this array to become glorious.

A "replace" means that you can choose any $i$ $(1\le i\le n)$ and assign $a_i=x$ where $x$ is an arbitrary integer (even if $x$ does not exist in the array).

Input

The first line contains a single integer $n$ ($2\le n\le 5\cdot 10^5$; $n$ is even), which denotes the length of the array.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 10^6)$.

Output

In a single line, output a single integer, which denotes the minimum amount of elements that need to be replaced in order for $a$ to become a glorious array.

Examples

Note

Optimal replacement sequence in test case 1:

$[2,6,4,6,2,9]\to [2,2,6,6,2,2]$ For this array both conditions hold:

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

• integer $2$ occurs more than $\frac{6}{2}=3$ times in our array.

We can show that this is the minimal amount of operations that we need to make.

In test case 2 the optimal replacement is:

$[3,7,2,4,9,3]\to [3,4,4,4,4,3]$

It can be shown that this is the smallest amount of operations that we need to do.

Scoring

You will receive at least $10$ points if your solution works correctly for $a_i=a_{i+1}$ for every $(1\le i<n)$.

You will receive at least $20$ points if your solution works correctly for $a_i=a_{n-i+1}$ for every $i$ $(1\le i\le n)$.

You will receive at least $30$ points if your solution works correctly for $n\le 1000$.

You will receive additional $40$ points if your solution works correctly without any restrictions.