解题思路
我们要统计满足下面条件的数对 (i,j)：
- 1≤i<j≤n
- ∣ai−aj∣=1
- 在 ai 和 aj 之间的所有数都严格大于 max(ai,aj)
先把题意转化一下。
P4814.第3题-米小游数字间隔
题目内容
米小游给定了一个长度为 n 的整数序列 a1,a2,…,an，请你统计有多少对 (i,j) 满足：
-
1≤i<j≤n
-
∣ai−aj∣=1
-
在 ai 和 aj 之间（不包括 ai 和 aj）的所有数字都严格大于 max(ai,aj)
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T (1≤T≤104) 代表数据组数，每组测试数据描述如下：
- 第一行一个整数 n (1≤n≤2×105)，表示序列 a 的长度。
- 第二行 n 个整数 a1,a2,…,an (1≤ai≤109)，表示数字序列。
除此之外，保证单个测试文件的 n 之和不超过 3×105。
输出描述
对于每组测试数据，输出一个整数表示满足条件的对数。
样例1
输入
2
5
1 3 2 4 1
4
2 2 2 2
输出
3
0
说明
第一组数据：
- (1,2): ∣1−3∣=2 不满足
- (1,3): ∣1−2∣=1，中间 3>2 满足
- (1,5): ∣1−1∣=0 不满足
- (2,3): ∣3−2∣=1，无中间数字 满足
- (2,4): ∣3−4∣=1，中间 2<4 不满足
- (3,4): ∣2−4∣=2 不满足
- (3,5): ∣2−1∣=1，中间 4>2 满足
共 3 对满足。
第二组数据：
所有数字相同，没有满足条件的对。
