区区区间间间

题号：NC20806
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

给出长度为n的序列a，其中第i个元素为

，定义区间(l,r)的价值为

$v_{l,r} = max(a_i - a_j | l \leqslant i,j\leqslant r)$

请你计算出 $\sum_{l = 1}^n \sum_{r = l + 1}^n v_{l,r}$

第一行输入数据组数T
对于每组数据，第一行为一个整数n，表示序列长度
接下来一行有n个数，表示序列内的元素

对于每组数据，输出一个整数表示答案

示例1

复制

3
3
4 2 3
5
1 8 4 3 9
20
2 8 15 1 10 5 19 19 3 5 6 6 2 8 2 12 16 3 8 17

复制

5
57
2712

对于一组测试数据的解释：
区间[1, 2]的贡献为：4 - 2 = 2
区间[1, 3]的贡献为：4 - 2 = 2
区间[2, 3]的贡献为：3 - 2 = 1
2 + 1 + 2 = 5.


不保证数据随机生成！