学习小组

题目描述:

在算法学院里，有一项名为学习小组的传统。班级里共有 $n$ 名同学，他们的座位排成一排，编号依次为 $1$ 到 $n$。经过开学初的基础能力测试，每位同学都获得了一个独一无二的编程能力值。我们用一个长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$ 来表示这 $n$ 名同学的能力值，即每位同学的能力值都在 $1$ 到 $n$ 之间且互不相同。

校长小C希望班级里能成立更多的“四人学习小组”。为了方便管理，一个学习小组必须由 $4$ 名同学组成，且他们的座位号必须严格递增。假设选出的四名同学座位号为 $a, b, c, d$，则必须满足 $a < b < c < d$。

在学习小组中，从左到右的四名同学分别担任以下角色：

• 座位号 $a$：逻辑先锋
• 座位号 $b$：代码达人
• 座位号 $c$：纠错助手
• 座位号 $d$：测试总监

校长小C经过多年教学发现，一个完美的学习小组必须同时满足以下两个神奇要求：

沟通要求：逻辑先锋（$a$）与纠错助手（$c$）需要高频讨论算法逻辑，两人的思维跨度不能太大。因此，他们的能力值差距不能超过常数 $K$，即满足 $\vert{}p_a - p_c\vert{} \le K$。

辅导要求：代码达人（$b$）与测试总监（$d$）之间需要形成老带新的互补关系。因此，他们的能力值必须有足够大的落差，差距至少为常数 $M$，即满足 $\vert{}p_b - p_d\vert{} \ge M$。

现在，小晨校长正在为即将到来的 S-PSC 和 PION 竞赛选拔人才。他拿到了 $T$ 个班级的测试数据，你能帮他编写一个程序，快速计算出每个班级中，到底能挑选出多少组不同的完美 $(a, b, c, d)$ 组合吗？

输入格式:

第一行包含一个正整数 $T$，表示班级（测试数据）的数量。

对于每个班级的测试数据：

第一行包含三个整数 $n, K, M$，分别表示班级的总人数，以及沟通要求与辅导要求中要求的常数 $K$ 和 $M$。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示按照座位号顺序排列的每位同学的编程能力值。保证该序列是一个 $1$ 到 $n$ 的排列。

输出格式:

输出共 $T$ 行。

每行输出一个整数，表示该班级中满足所有条件的完美学习小组 $(a, b, c, d)$ 的方案总数。

数据范围:

对于 $100\%$ 的数据，满足 $1 \le T \le 5$，$4 \le n \le 10000$，$0 \le K, M \le n$，$1 \le p_i \le n$，保证 $\sum n \le 30000$。

各测试点的数据范围梯度及特殊性质如下表所示：

样例输入:

样例1：
2
5 2 3
3 5 2 1 4
4 1 1
1 2 3 4

样例2：
1
7 4 2
2 6 3 1 7 4 5

样例3：
1
10 5 3
1 10 3 4 2 7 8 9 6 5

样例输出:

样例1：
1
0

样例2：
19

样例3：
84

提示:

样例解释 #2

所有的组合：

$(1, 2, 3, 4)$ $(1, 2, 3, 6)$ $(1, 2, 4, 6)$ $(1, 3, 4, 5)$ $(1, 3, 4, 7)$ $(1, 3, 6, 7)$ $(1, 4, 6, 7)$ $(1, 5, 6, 7)$ $(2, 3, 5, 7)$ $(2, 3, 6, 7)$ $(2, 4, 5, 6)$ $(2, 4, 5, 7)$ $(2, 4, 6, 7)$ $(2, 5, 6, 7)$ $(3, 4, 5, 6)$ $(3, 4, 5, 7)$ $(3, 4, 6, 7)$ $(3, 5, 6, 7)$ $(4, 5, 6, 7)$

来源: 温州市计算机学会