There are N stones in a pond, each having a value A_{i} written on it. A frog is at stone 1 and wants to reach stone N. The frog can jump from a stone i to any stone j (j>i). Let d be the length of subarray (i.e. j-i+1), then the energy required for the jump is $(d \cdot A_{i})-A_{j}.$ Find the minimum non-negative amount of energy required by the frog to reach the N-th stone.

Note: It is possible that the total amount of energy required is negative, in that case, you should print the minimum non-negative value (i.e. 0).

------ Input Format ------

• The first line contains an integer T - the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N - the number of stones.
• The second line contains N integers denoting the numbers written on the stones.

------ Output Format ------

For each test case output a single integer - the minimum non-negative energy required by the frog.

------ Constraints ------

$ 1 ≤T ≤2500 $ - the number of test cases
$ 1 ≤N ≤10^{5} $ - the number of stones.
$ 1 ≤A_{i} ≤10^{9} $ - the number written on stones.
- Sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

------ subtasks ------

Subtask 1 (5 points): $1 ≤N ≤10, 1 ≤A_{i} ≤100, \sum N ≤50$
Subtask 2 (10 points): $1 ≤N ≤100, 1 ≤A_{i} ≤100, \sum N ≤500$
Subtask 3 (15 points): $1 ≤N ≤1000, \sum N ≤5000$
Subtask 4 (70 points): original constraints

----- Sample Input 1 ------
4
3
6 1 3
4
3 1 10 4
3
7 9 1
2
1 5
----- Sample Output 1 ------
10
4
20
0
----- explanation 1 ------
- Test Case $1$: The frog can jump to the $2^{nd}$ stone from the $1^{st}$ stone, and then to the $3^{rd}$ stone from the $2^{nd}$ stone.
- Test Case $3$: The frog can jump to the $3^{rd}$ stone directly from the $1^{st}$ stone.
- Test Case $4$: The frog can jump to the $2^{nd}$ stone from the $1^{st}$ stone. However, the energy required in this case is negative (i.e. $-3$), So we will print $0$.

见题面

见题面