CF2241G.Summmon

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.

注意：本题的答案可能无法用 int64 或 long long 类型表示。建议使用 int128。

对于任意长度为 $m$ 的数组 $b$，定义 $f(b)$ 为：通过对 $b$ 执行以下操作任意多次后，所能达到的 $\max(b) - \min(b)$ 的最小可能值：

• 任选一个下标 $1 \le i \lt m$，并恰好执行以下操作之一：
  1. 将 $b_{i+1}$ 更新为 $b_{i+1} + b_i$，
  2. 将 $b_{i+1}$ 更新为 $b_{i+1} - b_i$。

给定一个长度为 $n$ 的数组 $a$。你的任务是计算 $f$ 在 $a$ 的所有子数组$^{\text{∗}}$ 上的取值之和。更准确地说，需计算如下表达式的值：

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

$^{\text{∗}}$ 若数组 $b$ 可通过从数组 $a$ 的开头删除若干（可能为零或全部）元素、再从结尾删除若干（可能为零或全部）元素而得到，则称 $b$ 是 $a$ 的一个子数组。特别地，一个数组是其自身的子数组。

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）—— 数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。

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])$.

对于每个测试用例，输出一个整数——即 $\sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r])$ 的值。

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$.

对于第一个测试用例，我们考察所有子数组：

• 对于单元素子数组 $[6]$、$[4]$ 和 $[8]$，无法执行任何操作，因此每个子数组的贡献均为 $0$。
• 对于 $[6,4]$，首元素固定为 $6$；第二个元素只能被修改为 $4+6=10$ 或 $4-6=-2$，此时差值（即 $\max - \min$）将变为 $4$ 或 $8$。因此，不执行任何操作是最优策略，其贡献为 $2$。
• 对于 $[4,8]$，我们选取 $i=1$ 并执行操作 $b_{2}:=b_{2}-b_{1}$，子数组变为 $[4,4]$，其贡献为 $0$。
• 对于 $[6,4,8]$，我们保持前两个元素不变，并选取 $i=2$，执行操作 $b_{3}:=b_{3}-b_{2}$，使 $8$ 变为 $4$。数组变为 $[6,4,4]$，因此 $\max(b)-\min(b)=6-4=2$。可以证明该值即为最优值。

因此，第一个测试用例的答案为 $0+0+0+2+0+2=4$。

对于第二个测试用例，所有长度为 $1$ 的子数组均贡献 $0$。在其余子数组中，仅有 $[2,3]$、$[3,4]$ 和 $[2,3,4]$ 具有非零贡献，且每个子数组的贡献均为 $1$。因此，答案为 $1+1+1=3$。