题目描述

Carol 有一个长度为 $n$ 的数组 $a$，他定义函数

$$f(l,r)=\sum_{i=l}^{r-1}\bigl(a_i-a_{i+1}\bigr),\quad 1\le l\le r\le n,$$

并规定 $f(i,i)=0$。

若

$$f(l,r)\ne(a_r-a_l),$$

则称子区间 $[l,r]\,(1\le l\le r\le n)$ 是不稳定 的。 Carol 想知道数组 $a$ 中共有多少个不稳定的子数组。

输入格式

• 第一行一个整数 $T$，表示测试数据组数。
• 对于每组数据：
  1. 第一行一个整数 $n$，表示数组长度；
  2. 第二行 $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,2],[2,3],[1,3]都是不稳定的。

数据范围