题目内容

在音频分析中，我们获得了一个长度为 $m$ 的采样序列 $a_1, a_2, \dots, a_m$。 对于一个长度至少为 3 的连续子段，如果该子段内除两端的每一个采样值 $a_i$ 都满足：$a_i \le a_{i-1}$ 且 $a_i \le a_{i+1}$，或者 $a_i \ge a_{i-1}$ 且 $a_i \ge a_{i+1}$（相等也算），就称该子段是一个理想波形段。

对于原序列的每一个非空连续子段：

• 若子段长度小于 3，则对答案贡献为 0。
• 若子段是理想波形段，则将它内部满足上述条件的采样点个数累加入答案（显然，这等于子段长度减去 2）。

请计算所有连续子段产生的总贡献，并对 $10^9+7$ 取模。

约束条件：

• 测试数据组数 $T$ 满足 $1 \le T \le 200000$。
• 每组数据中，序列长度 $m$ 满足 $1 \le m \le 200000$。
• 所有 $T$ 组数据的 $m$ 之和不超过 $200000$。
• 序列中每个元素的绝对值不超过 1000000000。
• 答案需对 1000000007 取模。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。 接下来依次描述每组数据： 每组数据的第一行包含一个整数 $m$，表示采样序列的长度。 第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$，表示采样值。

输出描述

对于每组测试数据，输出一行一个整数，表示该组数据的总贡献对 $10^9+7$ 取模后的结果。

样例1

输入

2
1
100
3
1 1 1

输出

0
1

说明

第一组数据：序列长度 1 < 3，不存在长度至少为 3 的子段，因此贡献为 0。

第二组数据：序列 [1, 1, 1]，长度 3。差分数组为 $d_1 = 1-1 = 0$，$d_2 = 1-1 = 0$，相邻差分乘积 $d_1 \times d_2 = 0 \le 0$，满足理想波形段条件。差分段长度 $s = 2$，贡献为 $\frac{s(s-1)(s+1)}{6} = \frac{2 \times 1 \times 3}{6} = 1$。

样例2

输入

1
4
2 2 2 2

输出

4

说明

序列 [2, 2, 2, 2]，长度 4。差分全为 0，任意相邻差分乘积均为 0，整个差分段长度 $s = 3$。

贡献公式 $\frac{s(s-1)(s+1)}{6} = \frac{3 \times 2 \times 4}{6} = 4$。从子段角度验证：长度为 3 的理想波形段有 [2,2,2]（索引 0..2）和 [2,2,2]（索引 1..3），各贡献 1；长度为 4 的理想波形段为整个数组，贡献 2。总和为 1+1+2=4。

样例3

输入

1
5
3 1 4 1 5

输出

10

说明

序列 [3, 1, 4, 1, 5]，长度 5。差分依次为 $-2, 3, -3, 4$，相邻乘积分别为 $(-2)\times 3 = -6 \le 0$，$3 \times (-3) = -9 \le 0$，$(-3) \times 4 = -12 \le 0$，所有相邻差分乘积均非正，构成一个完整的合法差分段，长度 $s = 4$。

贡献为 $\frac{4 \times 3 \times 5}{6} = 10$。即所有长度 $\ge 3$ 的子段都是理想波形段，内部满足条件的采样点个数之和为 10。

样例4

输入

1
8
1 2 3 2 1 2 3 4

输出

2

说明

序列 [1, 2, 3, 2, 1, 2, 3, 4]，长度 8。通过相邻差分乘积判断，该序列的差分段在以下位置出现不合法：

• 在 $i=2$ 处，$d_1=1, d_2=1$，乘积 $1>0$。
• 在 $i=4$ 处，$d_3=-1, d_4=-1$，乘积 $1>0$。
• 在 $i=6$ 处，$d_5=1, d_6=1$，乘积 $1>0$。

因此整个差分序列被切分为多段，合法段长度 $s$ 分别为 1、2、2、1。根据公式，仅 $s=2$ 贡献非零，每段贡献 $\frac{2 \times 1 \times 3}{6}=1$。两个 $s=2$ 的段总贡献为 2。