Sakurako and a Christmas Array#351

Sakurako and a Christmas Array

1.5 seconds
256 megabytes
Hard

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 is called glorious if the following holds:

You are given an array of length , where 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 (1\le i\le n) and assign a_i=x where is an arbitrary integer (even if does not exist in the array).

Input

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

The second line contains 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 to become a glorious array.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Optimal replacement sequence in test case 1:

[2,6,4,6,2,9]\to [2,\textcolor{red}{2,6},6,2,\textcolor{red}{2}] For this array both conditions hold:

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

  • integer 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,\textcolor{red}{4,4},4,\textcolor{red}{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 points if your solution works correctly for a_i=a_{i+1} for every (1\le i<n).

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

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

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