CF2227G.Drowning

Yousef has an array $a$ consisting of $n$ positive integers.

He defines a reduction operation on any array $c$ of length $|c| \ge 3$:

• Choose an index $i$ ($1 \lt i \lt |c|$) such that $c_{i-1} + c_{i+1} \gt c_i$.
• Replace the triplet ${c_{i-1}, c_i, c_{i+1}}$ with a single integer $x = c_{i-1} - c_i + c_{i+1}$.

The new integer $x$ occupies the position previously held by the triplet, and the length of the array decreases by $2$.

An array is considered good if it can be reduced to a single element by performing the operation above zero or more times. Note that an array of length $1$ is always good.

Yousef wants you to count the number of pairs $(l, r)$ ($1 \le l \le r \le n$) such that the subarray $a[l, r]$ is good.

优素福有一个由 $n$ 个正整数组成的数组 $a$。

他对任意长度为 $|c| \ge 3$ 的数组 $c$ 定义了一种约简操作：

• 选择一个下标 $i$（满足 $1 \lt i \lt |c|$），使得 $c_{i-1} + c_{i+1} \gt c_i$；
• 将三元组 $\{c_{i-1}, c_i, c_{i+1}\}$ 替换为单个整数 $x = c_{i-1} - c_i + c_{i+1}$。

新整数 $x$ 占据原三元组所在的位置，数组长度因此减少 $2$。

若一个数组能通过零次或多次执行上述操作被约简为仅含一个元素，则称该数组是好的。注意：长度为 $1$ 的数组总是好的。

优素福希望你统计满足条件的下标对 $(l, r)$（其中 $1 \le l \le r \le n$）的个数，使得子数组 $a[l, r]$ 是好的。

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of each test case follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

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

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示数组的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 表示数组的元素。

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

For each test case, output a single integer — the number of good subarrays.

对于每个测试用例，输出一个整数——即“好”子数组的个数。

In the first example, $a = [10, 20, 10]$. Subarrays $[10]$, $[20]$, and $[10]$ are all good ($3$ total). The subarray $[10, 20, 10]$ is not good. To reduce it, we must pick $i=2$. The condition $a_1 + a_3 \gt a_2$ becomes $10 + 10 \gt 20$, which is $20 \gt 20$ (false).

In the second example, $a = [1, 1, 1, 1, 1]$:

• All $5$ subarrays of length $1$ are good.
• All $4$ subarrays of length $2$ are not good.
• All $3$ subarrays of length $3$ (which are $[1, 1, 1]$) are good because $1 + 1 \gt 1$.
• All $2$ subarrays of length $4$ are not good.
• The subarray of length $5$ is good: $[1, 1, 1, 1, 1] \xrightarrow{i=2} [1, 1, 1] \xrightarrow{i=2} [1]$.
• Total good subarrays $= 5 + 3 + 1 = 9$.

在第一个例子中，$a = [10, 20, 10]$。子数组 $[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$。