Nils likes sorted permutations. He currently has a permutation of the first positive integers
, and wishes to sort it. He can apply the following operation any number of times:
- Choose integers
satisfying
. Then, sort the subarray
, leaving the other elements unchanged. The cost of the operation is
.
For example, if the permutation was , and Nils chooses
and
, then the permutation will become
, incurring a cost of
.
What is the minimum total cost to sort the permutation?
Constraints
is a permutation of the integers
, that is, every integer between
and
(inclusive) occurs exactly once in
.
Subtask 1 [20%]
There exists an optimal solution which applies at most one operation.
Subtask 2 [20%]
Subtask 3 [60%]
No additional constraints.
Input Specification
The first line contains a single integer, .
The second line contains space-separated integers,
.
Output Specification
On a single line, output the minimum total cost to sort Nils' permutation.
Sample Input
6
2 1 3 6 5 4
Sample Output
5
Explanation
It is optimal to first sort the subarray with and
. Then, the subarray with
and
can be sorted.
Comments