You are given a permutation \(p_1, p_2, ..., p_n\) of numbers from \(1\) to \(n\).

A permutation \(p_1, p_2, ..., p_n\), beauty, is defined as the minimum number of adjacent swaps required to sort the permutation.

If it is allowed to swap two elements of the permutation (not necessarily adjacent) at most once, then what is the minimum beauty that you can get?

Input format

The first line contains \(n\).
The second line contains the space-separated permutation \(p_1, p_2, ..., p_n\).

Output format

Print an integer denoting the minimum ugliness that we can get.

Constraints

\(1 \leq n \leq 7000\)

\(1 \leq p_i \leq n\), all \(p_i\) are distinct