Minimum Cost to Sort a Permutation

You are given a permutation (p_1, p_2, \ldots, p_n) of length (n). Your task is to sort the permutation so that for every (i = 1, 2, \ldots, n), (p_i = i).

You are allowed to perform the following operation any number of times:

• Choose a contiguous subarray \([l, r]\) (\(1 \le l \le r \le n\)) and sort the elements in that subarray in increasing order. The cost of this operation is \(r-l+1\), which is the length of the chosen interval.

Determine the minimum total cost required to completely sort the permutation.

Observation: If the permutation is already sorted, the cost is \(0\). Otherwise, let \(l\) be the smallest index where \(p_l \neq l\) and \(r\) be the largest index where \(p_r \neq r\). Then, sorting the subarray \([l, r]\) (which contains exactly the numbers \(l, l+1, \ldots, r\)) will yield a sorted permutation at a cost of \(r-l+1\).

inputFormat

The first line contains a single integer (n) ((1 \le n \le 10^5)) — the length of the permutation.

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

outputFormat

Output a single integer denoting the minimum total cost required to sort the permutation.

sample

4
1 3 2 4

2

</p>