U122190 计数 Count
题目背景
#### 2020.7.15 考试
[题解](https://www.cnblogs.com/wondering-world/p/13333966.html)
题目描述
小 A 是一名热衷于优化各种算法的 OIER,有一天他给了你一个随机生成的 $1~n$ 的排列，并定
义区间$[l,r]$的价值为：
### $C_{l,r} = max(a_i - a_j | l \le i,j \le r) $
他想请你告诉他，所有区间的价值的总和为多少
输入格式
第一行一个数 $T$ ，表示数据组数
对于每一组数据：
第一行一个数 $n$（$1 \le n,m \le 100,000$）
第二行 $n$ 个数 $a_1$ ~ $a_n$，表示一个 $1$~$n$ 的随机的排列
输出格式
对于每组数据输出一个数，表示答案
说明/提示
对于 $60%$的数据：$n \le 1000$
对于 $100%$的数据，$n \le 100,000$