稳定区间[上海2025年5月月赛丙组3]

内存限制: 256 Mb时间限制: 1000 ms

题目描述

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] (1≤l≤r≤n)$ 是不稳定的。

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

输入格式

第一行一个整数 T 表示数据组数， 对于每组数据：第一行一个整数 n 表示数组长度。

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

输出格式

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

数据范围

对于 30% 的数据， $∑n≤1000，0≤a_i ≤1。$ 对于 60% 的数据， $∑n≤10^5 ，0≤a_i≤1。$

对于 100% 的数据， $1≤T≤10^5 ，n≥1，∑n≤10^5 ，0≤a_i​ ≤10^9 。$

样例数据

输入:

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

输出:

3
4
10

说明:

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