首页 > 试题广场 >

Balanced Array

[编程题]Balanced Array
\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
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 3浏览

热门推荐

相关试题

Balanced Array

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号