A16880 · Summmon · GESP考级

题目描述

对于任意长度为 $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])$ 的值。

输入 #1

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

输出 #1