L. 简单的区间问题
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定一个长度为 $$$n$$$ 的序列 $$$a$$$，我们定义一个子区间$$$^\dagger$$$ $$$[l,r]$$$ 的权值 $$$f(a[l\dots r]) = \max_{i=l}^{r} a_i+\min_{i=l}^r a_i$$$，即区间最大值与区间最小值之和。

你需要求出所有子区间权值的总和，即求 $$$\sum_{i=1}^n\sum_{j=i}^n f(a[i\dots j])$$$。

$$$\dagger$$$ 子区间：一个序列 $$$a$$$ 的子区间 $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) 定义为原序列中连续的一段元素：$$$a_l, a_{l+1}, \dots, a_r$$$，记作 $$$a[l\dots r]$$$ 的总和值。

Input

第一行输入一个正整数 $$$T(1\le T\le 10^4)$$$，表示数据组数。

接下来的 $$$T$$$ 组数据中，每组数据输入如下：

  • 第一行输入一个正整数 $$$n(1\le n\le 2\times 10^5)$$$，表示序列长度。
  • 第二行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\dots,a_n(1\le a_i\le 10^8)$$$。

此外，数据保证所有测试组 $$$n$$$ 的总和不超过 $$$2\times 10^5$$$。

Output

对于每组测试，共输出一行一个整数，表示答案。

Example
Input
6
3
5 3 7
6
1 5 4 2 8 5
6
1 4 2 6 3 3
9
9 9 8 2 4 4 3 5 3
7
12 5 3 10 4 18 11
12
1 1 4 5 1 4 1 9 1 9 8 10
Output
58
181
147
448
505
710
Note

对于第一组测试：

  • $$$f(a[1])=5+5=10$$$，$$$5$$$ 同时是该区间最大值和最小值。
  • $$$f(a[2])=3+3=6$$$，$$$3$$$ 同时是该区间最大值和最小值。
  • $$$f(a[3])=7+7=14$$$，$$$7$$$ 同时是该区间最大值和最小值。
  • $$$f(a[1\dots 2])=5+3=8$$$，$$$5$$$ 是该区间的最大值，$$$3$$$ 是该区间的最小值。
  • $$$f(a[2\dots 3])=7+3=10$$$，$$$7$$$ 是该区间的最大值，$$$3$$$ 是该区间的最小值。
  • $$$f(a[1\dots 3])=7+3=10$$$，$$$7$$$ 是该区间的最大值，$$$3$$$ 是该区间的最小值。