?Time Limit: 3000 MS Memory Limit: 65536 K


Description

“很多年以后,CaCO3将会想起做那道名叫简单区间题的那个遥远的下午。”

那道题目是这样的:

给你一个整数序列,长度为,问其中所有区间的最小值之和。

即:

Input

第1行为组数T.

接下来T组,每组包含两行。

第一行为长度

第二行为N个数,保证将会是随机在范围内的一个数。

Output

对于每个询问输出相应的答案。

Sample Input

2

3

1 2 3

5

5 4 3 2 1

Sample Output

10

35

Note

对于样例1:

[1,1] min=1

[1,2] min=1

[1,3] min=1

[2,2] min=2

[2,3] min=2

[3,3] min=3