## Yet Another Contest 8 P1 - Permutation Sorting

View as PDF

Points: 5 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

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 .

There exists an optimal solution which applies at most one operation.

#### 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.