该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目：稳定区间

题目描述

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$（$1\leq T\leq10^5$ ），表示数据组数。
• 对于每组数据：
  • 第一行：一个整数 $n$（$n\geq1$ ），表示数组长度。
  • 第二行：$n$ 个整数 $a_1, a_2, \cdots, a_n$（$0\leq a_i\leq10^9$ ），表示数组 $a$ 的元素 。

输出格式

对于每组数据，输出一行，一个整数表示数组 $a$ 中不稳定子区间的数量。

数据范围

• 对于 $30\%$ 的数据，$\sum n\leq1000$ ，$0\leq a_i\leq1$ 。
• 对于 $60\%$ 的数据，$\sum n\leq10^5$ ，$0\leq a_i\leq1$ 。
• 对于 $100\%$ 的数据，$1\leq T\leq10^5$ ，$n\geq1$ ，$\sum n\leq10^5$ ，$0\leq a_i\leq10^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]$ 都是不稳定的。