G. Summmon
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Note that the answer for this problem might not fit in int64 or long long. It is recommended to use int128.

For any array $$$b$$$ of length $$$m$$$, define $$$f(b)$$$ as the minimum possible value of $$$\max(b) - \min(b)$$$ that can be achieved by performing the following operation any number of times:

  • Choose any index $$$1 \le i \lt m$$$, and do exactly one of the following:
    1. Set $$$b_{i+1} := b_{i+1} + b_i$$$,
    2. Set $$$b_{i+1} := b_{i+1} - b_i$$$.

You are given an array $$$a$$$ of length $$$n$$$. Your task is to compute the sum of $$$f$$$ over all the subarrays$$$^{\text{∗}}$$$ of $$$a$$$. More formally, determine the value of

$$$$$$\sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r]).$$$$$$

$$$^{\text{∗}}$$$An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of each test case follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test case, print a single integer — the value of $$$\sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r])$$$.

Example
Input
5
3
6 4 8
4
1 2 3 4
9
9 9 8 2 4 4 3 5 3
6
18 12 24 9 6 36
6
36 24 18 12 9 6
Output
4
3
39
72
111
Note

For the first test case, let us look at all subarrays.

  • For the single-element subarrays $$$[6]$$$, $$$[4]$$$, and $$$[8]$$$, no operation can change anything, so each of them contributes $$$0$$$.
  • For $$$[6,4]$$$, the first element is fixed as $$$6$$$. The second element can only be changed to $$$4+6=10$$$ or $$$4-6=-2$$$, so the gap would become $$$4$$$ or $$$8$$$. Hence, doing no operation is best, and the contribution is $$$2$$$.
  • For $$$[4,8]$$$, we choose $$$i=1$$$ and apply $$$b_{2}:=b_{2}-b_{1}$$$. Then the subarray becomes $$$[4,4]$$$, so its contribution is $$$0$$$.
  • For $$$[6,4,8]$$$, we keep the first two elements as they are and choose $$$i=2$$$. Then we apply $$$b_{3}:=b_{3}-b_{2}$$$, so $$$8$$$ becomes $$$4$$$. The array becomes $$$[6,4,4]$$$, and therefore $$$\max(b)-\min(b)=6-4=2$$$. It can be shown that this is the optimal value.

Therefore, the answer for the first test case is $$$0+0+0+2+0+2=4$$$.

For the second test case, every subarray of length $$$1$$$ contributes $$$0$$$. Among the remaining subarrays, only $$$[2,3]$$$, $$$[3,4]$$$, and $$$[2,3,4]$$$ have a non-zero contribution, each contributing $$$1$$$. Therefore, the answer is $$$1+1+1=3$$$.


Morty Proxy This is a proxified and sanitized view of the page, visit original site.