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:
for every (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 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).
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).
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.
Example 1
Example 2
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.
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.