题目描述

小 C 有一个元素两两不同的长度为 $n$ 的序列 $A$，但是这个序列可能是无序的。

小 C 不喜欢无序的序列，他现在可以做以下操作任意次：

• 任意选择一个区间 $[l,r]$，花费 $r-l$ 的代价将区间 $[l,r]$ 中的数从小到大排序。

小 C 想用最小的代价和让序列 $A$ 有序（从小到大），但他不仅仅只满足于求出让序列 $A$ 有序的最小代价。

小 C 设 $f_{l,r}$ 表示在只考虑序列 $A$ 的区间 $[l,r]$ 的前提下，让子序列 $[A_l,A_{l+1},...,A_r]$ 有序的最小代价和。

他想请你求出

的值。

输入格式

输入的第一行包含一个整数 $n$。

接下来一行包含 $n$ 个整数，第 $i$ 个整数表示 $A_i$。

输出格式

共一行，输出一个整数。

3
3 10 6

2

5
9 8 2 4 6

16

数据范围

样例 1 解释

$f_{1,1}=f_{2,2}=f_{3,3}=0$。 $f_{1,2}=0,f_{2,3}=1$。 $f_{1,3}=1$。

• 对于 $20\%$ 的数据，保证 $n\le 5$。
• 对于 $40\%$ 的数据，保证 $n\le 16$。
• 对于 $60\%$ 的数据，保证 $n\le 500$。
• 对于 $80\%$ 的数据，保证 $n\le 5000$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 3\times 10^5$，$1\le A_i\le 10^9$，保证序列 $A$ 中元素两两不同。