题目描述

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

输出格式

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

样例

4
3
10 20 10
5
1 1 1 1 1
4
5 1 5 1
1
100

3
9
5
1

样例说明

在第一个例子中，$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 完成。

来源

Codeforces 2227G，英文题名 Drowning。