【问题描述】

小 A 是一名热衷于优化各种算法的 OIER，有一天他给了你一个随机生成的 1~n 的排列 a，并定义区间 $[l,r]$ 的价值为：

$C_{l,r} = max( a_{i}-a_{j}$ | $l<=i,j<=r )$

他想请你告诉他，所有区间的价值的总和为多少。

【输入】

第一行一个数 T，表示数据组数

对于每一组数据：

第一行一个数 n

第二行 n 个数 a1...an，表示一个 1~n 的随机的排列

【输出】

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

【输入输出样例】

输入

1
4
3 2 4 1 

输出

14 

【数据范围】

对于 60%的数据：1<=n<=1000

对于 100%的数据，1<=n<=100,000， 1<=T<=10