给定一个长度为 n 的正整数序列 a_1,a_2,\ldots,a_n,以及一个正整数 k。
如果两个不同位置的元素 a_i 和 a_j 满足:
那么称 (i,j) 为一个合法数对。
请你计算序列中一共有多少个合法数对。
注意:即使两个位置上的数字相同,只要位置不同,也应当视为不同的元素。
第一行输入两个正整数 n,k,分别表示序列长度和允许的最大差值。
第二行输入 n 个正整数 a_1,a_2,\ldots,a_n。
输出一个整数,表示合法数对的总数量。
5 2 1 3 5 2 4
7
满足条件的数对共有 7 个:
因此答案为 7。
对于所有测试数据,保证:
本题采用子任务评分,每个子任务包含若干测试点。
| 子任务 | 分值 | 特殊限制 |
|---|---|---|
| 1 | 30 分 | 1\le n\le 3000 |
| 2 | 30 分 | 1\le n\le 10^5,且 1\le a_i\le 1000 |
| 3 | 40 分 | 无额外限制 |
每个子任务只有全部测试点通过才能获得对应分数。