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 books. Each book has a unique integer height between and (that is, the heights of the books form a permutation of the integers from to ). The robot has 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 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 of the line, the robot can only swap the book with the 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 is , as there are two subsections: (decreasing) and (increasing). The instability of line is only . 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.
The first line will contain the integer , the number of books in the line.
The second line will contain integers, , the heights of the books. The integers are guaranteed to form a permutation of the integers .
Output the minimum instability of the line of books, given that you can perform an infinite number swaps between indices and for some .
Subtask 1 [10%]
Subtask 2 [50%]
Subtask 3 [40%]
No further constraints.
Sample Input 1
4 4 1 3 2
Sample Output 1
Explanation For Sample 1
One way to achieve the minimum instability is to perform the swap once on index to achieve , which has an instability of . 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