4361: T4 排序（sort）
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
## T4 排序（sort）
### 题目描述
小 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]$ 有序的最小代价和。
他想请你求出
$$
\sum_{i=1}^n \sum_{j=i}^n f_{i,j}
$$
的值。
输入
### 输入格式
输入的第一行包含一个整数 $n$。
接下来一行包含 $n$ 个整数，第 $i$ 个整数表示 $A_i$。
输出
### 输出格式
共一行，输出一个整数。
样例输入 复制
3
3 10 6样例输出 复制
2提示
### 样例 1 输入
```
3
3 10 6
```
### 样例 1 输出
```
2
```
### 样例 1 解释
$f_{1,1}=f_{2,2}=f_{3,3}=0$。
$f_{1,2}=0,f_{2,3}=1$。
$f_{1,3}=1$。
### 样例 2 输入
```
5
9 8 2 4 6
```
### 样例 2 输出
```
16
```
其余样例见下发文件。
### 数据规模与约定
- 对于 $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$ 中元素两两不同。