题目描述

Carol 有一个长度为 $n$ 的数组 $a$，他定义函数 $f(l,r)=\sum_{i=l}^{r-1}(a_i-a_{i+1})$，其中 $1\leq l\leq r\leq n$，特殊地，$f(i,i)$ 定义为 $0$。

如果 $f(l,r)\neq (a_r-a_l)$，则称一个子区间 $[l,r](1\leq l\leq r\leq n)$ 是不稳定的。

Carol 想知道数组 $a$ 有多少个不稳定的子数组。

输入格式

第一行一个整数 $T$ 表示数据组数，对于每组数据：

第一行一个整数 $n$ 表示数组长度。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$ 表示数组 $a$。

输出格式

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

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

3
4
10

样例解释 1

对于第一组数据，子区间[1,2],[2,3],[1,3]都是不稳定的。

数据范围

对于 $30\%$ 的数据，$\sum n\leq 1000$，$0\leq a_i\leq 1$。

对于 $60\%$ 的数据，$\sum n\leq 10^5$，$0\leq a_i\leq 1$。

对于 $100\%$ 的数据，$1\leq T\leq 10^5$，$n\ge 1$，$\sum n\leq 10^5$，$0\leq a_i\leq 10^9$。