Andy is getting bored in English class, and so he decides to pull out his laptop and start playing his favourite game!

In this game, Andy controls a stationary robot that stands in the center of a line of $N$ books. Each book has a unique integer height between $1$ and $N$ (that is, the heights of the books form a permutation of the integers from $1$ to $N$). The robot has $2$ arms that can only extend outward perpendicular to the robot's body to any length. These arms have a very unique property: Extending one arm to some length extends the other arm to the same length.

Andy must use the robot's arms to take $2$ books and swap their positions in the line. However, given the arm's unique property, the robot can only swap books that are equally distant to the robot's location (the center of the line of books). Formally, if one arm is at index $i$ of the line, the robot can only swap the $i^{\text{th}}$ book with the $N-i+1^{\text{th}}$ book.

The line of books is very unstable! Define the instability of the line as the minimum number of increasing and decreasing subsections of books. For example, the instability of the line $[3,1,2,4]$ is $2$, as there are two subsections: $[3,1]$ (decreasing) and $[1,2,4]$ (increasing). The instability of line $[1,2,3]$ is only $1$. The goal of the game is to minimize the instability of the resulting line of books using the robot's swaps.

The game does not care about how many times swaps are made. It only cares about the final instability. Can you find the minimum possible instability that Andy should strive for?

Python users are recommended to use PyPy over CPython. There is a significant performance increase.

Input Specification

The first line will contain the integer $N$ $(1\le N\le 5\cdot {10}^5)$, the number of books in the line.

The second line will contain $N$ integers, $h_i$ $(1\le h_i\le N)$, the heights of the books. The $N$ integers are guaranteed to form a permutation of the integers $1,\dots ,N$.

Output Specification

Output the minimum instability of the line of books, given that you can perform an infinite number of swaps between indices $i$ and $N-i+1$ for some $1\le i\le N$.

Constraints

Subtask 1 [10%]

$N\le 40$

Subtask 2 [50%]

$N$ is even.

Subtask 3 [40%]

No additional constraints.

Sample Input 1

4
4 1 3 2

Sample Output 1

2

Explanation For Sample 1

One way to achieve the minimum instability is to perform the swap once on index $2$ to achieve $[4,3,1,2]$, which has an instability of $2$. Note that there could be multiple ways to achieve the minimum instability.

Sample Input 2

8
1 3 8 7 5 2 6 4

Sample Output 2

3