解题思路

我们要统计满足下面条件的数对 $(i,j)$：

• $1 \le i < j \le n$
• $|a_i-a_j|=1$
• 在 $a_i$ 和 $a_j$ 之间的所有数都严格大于 $\max(a_i,a_j)$

先把题意转化一下。

题目内容

米小游给定了一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，请你统计有多少对 $(i,j)$ 满足：

• $1 \le i < j \le n$

• $|a_i - a_j| = 1$

• 在 $a_i$ 和 $a_j$ 之间（不包括 $a_i$ 和 $a_j$）的所有数字都严格大于 $\max(a_i,a_j)$

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1 \le T \le 10^4)$ 代表数据组数，每组测试数据描述如下：

• 第一行一个整数 $n\ (1 \le n \le 2 \times 10^5)$，表示序列 $a$ 的长度。
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n\ (1 \le a_i \le 10^9)$，表示数字序列。

除此之外，保证单个测试文件的 $n$ 之和不超过 $3 \times 10^5$。

输出描述

对于每组测试数据，输出一个整数表示满足条件的对数。

样例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$ 对满足。

第二组数据：

所有数字相同，没有满足条件的对。