题目描述

Carol 有一个长度为 n 的数组 a，他定义函数 f(l, r) = Σ(i从l到r-1)(a_i - a_{i+1})，其中 1 ≤ l ≤ r ≤ n。特殊地，f(i, i) 定义为 0。 如果 f(l, r) ≠ (a_r - a_l)，则称子区间 [l, r] 是不稳定的。请计算数组中不稳定子区间的数量。

输入格式 第一行一个整数 T 表示数据组数。 对于每组数据： 第一行一个整数 n 表示数组长度。 第二行 n 个整数 a_1, a_2, ..., a_n 表示数组元素。

输出格式 每组数据输出一行一个整数，表示答案。

数据范围 对于 30% 数据：∑n ≤ 1000，0 ≤ a_i ≤ 1 对于 60% 数据：∑n ≤ 1e5，0 ≤ a_i ≤ 1 对于 100% 数据：1 ≤ T ≤ 1e5，n ≥ 1，∑n ≤ 1e5，0 ≤ a_i ≤ 1e9

3
3
10 20 30
4
1 2 1 2
5
1 2 3 4 5

3
4
10