题目描述

现在有一个长度为 $n$ 的数组，小 H 想研究这个数组的某一个性质，他提出了一个"山峰数组"的概念。即：由三个元素组成的 $[b_1,b_2,b_3]$，满足 $b_2>b_1$ 且 $b_2>b_3$。他将选择两个索引 $l,r$ $(1\le l<r< n)$，然后分成三个非空的连续子数组，我们记

$$b_1=\sum_{i=1}^l a_i ,\ \ b_2=\sum_{i=l+1}^r a_i ,\ \ b_3=\sum_{i=r+1}^n a_i $$

求有多少个不同的 $(l,r)$ 满足 $[b_1,b_2,b_3]$ 是一个山峰数组。

输入格式

第一行 $1$ 个整数 $T$ ($1\le T \le 100$)，代表测试样例个数。

接下来的每个测试样例有 $2$ 行。

第一行 $1$ 个正整数 $n$ ($1\le n \le 2 \times 10^5$) ，表示数组个数。

第二行 $n$ 个整数 $a_i$ ($1\le a_i \le 10^9$)，代表每个数组元素的值。

数据保证 $\sum n \le 2 \times 10^5$。

输出格式

输出 $T$ 行，每行一个正整数，表示满足山峰数组区间的个数。

输入样例

2
5
1 2 3 4 5
5
1 2 3 2 1

输出样例

2
3

提示

对于第一个样例：

我们可以找到两对 $(l,r)$ 即：$(1,4),(2,4)$

对于第二个样例：

我们可以找到三对 $(l,r)$ 即：$(1,3),(1,4),(2,4)$