Sorting Proximity

As a New Year's resolution, our heroes want everything around them to be clean and perfectly arranged. Thus, they now want to apply their new ideals on their daily work, namely handling the various data structures they are using.

This time around, they got an array of length $n$ and they define the sorting proximity of the array as the number of swaps which have to be done in order to sort the array, if we use the bubble sort algorithm.

Namely, as long as the array is not sorted yet, the bubble sort algorithm iterates through the array and every time two adjacent values are wrongly placed relative to one another, they are swapped. The sorting proximity is the number of times this happens during the algorithm.

For example, if we have the array [$4, 2, 3, 5, 1$], the sorting proximity of the array is $6$.

Now, our heroes want to improve the sorting proximity of the array and they asked for your help. Your job is to swap two integers from the array (they don't have to be adjacent) so that the sorting proximity of the resulting array is minimal. Even though the swap may not improve the answer, you must do it.

Input data

The first line of the input contains $n$, the number of integers from the array.

Output data

The output contains the minimal sorting proximity we can get if we swap exactly two values from the array.

Constraints and clarifications

• $1 \leq n \leq 10^5$
• $1 \leq v_i \leq 10^9$
• For tests worth $20$ points, $1 \leq n \leq 10^3$
• For tests worth $40$ more points, all the values from the array are distinct.

Example 1

stdin

5
5 2 4 3 1

stdout

1

Explanation

For the first sample test case, we can swap $5$ and $1$ and we will get the array [$1, 2, 4, 3, 5$] which has the sorting proximity equal to $1$.

Example 2

stdin

5
3 1 7 9 5

stdout

2

Explanation

For the second sample test case, we can swap $5$ and $7$ and we will get the array [$3, 1, 5, 9, 7$] which has the sorting proximity equal to $2$.