Nils likes sorted permutations. He currently has a permutation of the first ~N~ positive integers ~p_1, p_2, \dots, p_N~, and wishes to sort it. He can apply the following operation any number of times:

• Choose integers ~l, r~ satisfying ~1 \le l \le r \le N~. Then, sort the subarray ~p_l, p_{l+1}, \dots, p_r~, leaving the other elements unchanged. The cost of the operation is ~r-l+1~.

For example, if the permutation was ~1, 5, 3, 4, 2~, and Nils chooses ~l = 2~ and ~r = 4~, then the permutation will become ~1, 3, 4, 5, 2~, incurring a cost of ~3~.

What is the minimum total cost to sort the permutation?

Constraints

~1 \le N \le 10^6~

~p_1, p_2, \dots, p_N~ is a permutation of the integers ~1, 2, \dots, N~, that is, every integer between ~1~ and ~N~ (inclusive) occurs exactly once in ~p~.

Subtask 1 [20%]

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

Subtask 2 [20%]

~1 \le N \le 2000~

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains a single integer, ~N~.

The second line contains ~N~ space-separated integers, ~p_1, p_2, \dots, p_N~.

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 ~l = 1~ and ~r = 2~. Then, the subarray with ~l = 4~ and ~r = 6~ can be sorted.