← 返回题目列表

Codeforces · 2227/G

G. 溺水

中文机器翻译题面 查看原题

Yousef 有一个数组 $$$a$$$,由 $$$n$$$ 正整数组成。

他定义了对任何长度为 $$$|c| 的数组 $$$c$$$ 的归约操作\ge 3$$$:

  • 选择索引 $$$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$$$ 的数组总是好的。

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 \cdot 10^5$$$) — 数组的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^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]$$$。子数组 $$$[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]$$$:

  • 所有长度为 $$$1$$$ 的 $$$5$$$ 子数组都很好。
  • 所有长度为 $$$2$$$ 的 $$$4$$$ 子数组都不好。
  • 所有长度为 $$$3$$$ 的 $$$3$$$ 子数组(即 $$$[1, 1, 1]$$$)都很好,因为 $$$1 + 1 \gt 1$$$。
  • 所有长度为 $$$4$$$ 的 $$$2$$$ 子数组都不好。
  • 长度为 $$$5$$$ 的子数组很好:$$$[1, 1, 1, 1, 1] \xrightarrow{i=2} [1, 1, 1] \xrightarrow{i=2} [1]$$$。
  • 好子数组总数 $$$= 5 + 3 + 1 = 9$$$。