Minimum Operations to Sort a Permutation

You are given a permutation \(p\) of \(\{1,2,\dots,n\}\). You are allowed to perform two types of operations on \(p\):

• Cycling operation: Swap two adjacent elements in \(p\).
• Crazy operation: Remove the smallest element in \(p\) (this operation cannot be performed if \(p\) is empty).

Your goal is to make the sequence strictly increasing with the minimum number of operations.

Note: After performing some crazy operations, if you remove \(k\) elements then the remaining sequence will consist of the numbers \(k+1, k+2, \dots, n\) in the order they appeared in the original permutation. In order to make the sequence strictly increasing, you may need to perform some cycling operations (i.e. adjacent swaps) on the remaining sequence. The number of swaps required to sort a sequence is equal to its inversion count.

Find the minimum number of operations required to transform \(p\) into a strictly increasing sequence.

Mathematical Formulation:

Let \(f(0)\) be the inversion count of the full permutation. For \(k \ge 1\), after removing the smallest \(k\) elements (i.e. \(1,2,\dots,k\)), let \(f(k)\) be the inversion count of the remaining sequence. Then, you need to compute:

\[ \min_{0 \le k \le n} \{ k + f(k) \}. \]

inputFormat

The first line contains an integer \(n\), the size of the permutation.

The second line contains \(n\) space-separated integers representing the permutation \(p\) of \(\{1,2,\dots,n\}\).

outputFormat

Output a single integer, the minimum number of operations needed to make the sequence strictly increasing.

sample

3
1 2 3

0

</p>