CF2227G Drowning

Yousef 有一个数组 $a$，里面装着 $n$ 个正整数。 他定义了一个针对长度为 $|c| \ge 3$ 的数组 $c$ 的“缩减操作”： - 选一个下标 $i$（满足 $1 \lt i \lt |c|$），条件是 $c_{i-1} + c_{i+1} \gt c_i$。 - 用一个整数 $x = c_{i-1} - c_i + c_{i+1}$ 替换掉三元组 $\{c_{i-1}, c_i, c_{i+1}\}$。 新整数 $x$ 就占据原来三元组的位置，数组长度因此缩短了 $2$。 如果一个数组能通过零次或多次这样的操作，最终缩减成只有一个元素，我们就称它是*好数组*。注意，长度为 $1$ 的数组永远是好数组。 Yousef 想让你数一数，有多少对 $(l, r)$（满足 $1 \le l \le r \le n$）使得子数组 $a[l, r]$ 是好数组。

第一行是一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行是整数 $n$（$1 \le n \le 2 \times 10^5$）——数组大小。 第二行有 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——数组元素。 保证所有测试用例中 $n$ 的总和不超过 $2\times10^5$。

每个测试用例输出一个整数——好子数组的数量。

在第一个例子中，$a = [10, 20, 10]$。长度为 1 的子数组 $[10]$、$[20]$ 和 $[10]$ 都是好数组（共 $3$ 个）。而整个子数组 $[10, 20, 10]$ 不是好数组。因为缩减时必须选 $i=2$，条件 $a_1 + a_3 \gt a_2$ 变成 $10 + 10 \gt 20$，即 $20 \gt 20$，显然不成立。 在第二个例子中，$a = [1, 1, 1, 1, 1]$： - 所有 $5$ 个长度为 $1$ 的子数组都是好数组。 - 所有 $4$ 个长度为 $2$ 的子数组都不是好数组。 - 所有 $3$ 个长度为 $3$ 的子数组（即 $[1, 1, 1]$）都是好数组，因为 $1 + 1 \gt 1$。 - 所有 $2$ 个长度为 $4$ 的子数组都不是好数组。 - 长度为 $5$ 的子数组是好数组：$[1, 1, 1, 1, 1] \xrightarrow{i=2} [1, 1, 1] \xrightarrow{i=2} [1]$。 - 好子数组总数是 $= 5 + 3 + 1 = 9$。 翻译由 ChatGPT 4.1 完成。