CF2241G.Summmon

对于任意长度为 $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$ 的一个子数组。特别地，一个数组是其自身的子数组。

第一行包含一个整数 $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$。

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

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

• 对于单元素子数组 $[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$。