Balanced Array
题号:NC313662
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小苯有一个长度为 n 的数组 a_1, a_2, \dots, a_n

\hspace{15pt}定义数组的一个子数组 a_l, a_{l+1}, \dots, a_r平衡的,当且仅当满足:

\max(a_l, a_{l+1}, \dots, a_r) - \min(a_l, a_{l+1}, \dots, a_r) \leqq 1

\hspace{15pt}小苯想要知道,有多少个整数对 (l, r) 满足 1 \leqq l \leqq r \leqq n,且子数组 a_l, a_{l+1}, \dots, a_r 是平衡的。
\hspace{15pt}你的任务就是求出满足条件的整数对数量。

输入描述:

\hspace{15pt}每个测试文件包含多组测试数据。第一行输入一个整数 T\left(1 \leqq T \leqq 10^4 \right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行输入一个整数 n\left(1 \leqq n \leqq 2 \times 10^5 \right)
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n\left(1 \leqq a_i \leqq 10^9 \right)

\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 2 \times 10^5

输出描述:

\hspace{15pt}对于每组数据,新起一行输出一个整数,表示满足条件的整数对 (l, r) 的数量。
示例1

输入

复制
3
4
1 2 2 3
5
1 1 1 1 1
3
1 3 5

输出

复制
9
15
3