241987 - 数对统计(pair)

题目描述

给定一个长度为 n 的正整数序列 a_1,a_2,\ldots,a_n,以及一个正整数 k。

如果两个不同位置的元素 a_i 和 a_j 满足:

  1. 1\le i
  2. |a_i-a_j|\le k

那么称 (i,j) 为一个合法数对。

请你计算序列中一共有多少个合法数对。

注意:即使两个位置上的数字相同,只要位置不同,也应当视为不同的元素。

输入

第一行输入两个正整数 n,k,分别表示序列长度和允许的最大差值。

第二行输入 n 个正整数 a_1,a_2,\ldots,a_n。

输出

输出一个整数,表示合法数对的总数量。

样例

输入

5 2
1 3 5 2 4

输出

7
说明

样例解释

满足条件的数对共有 7 个:

  • (1,2):|1-3|=2
  • (1,4):|1-2|=1
  • (2,4):|3-2|=1
  • (2,5):|3-4|=1
  • (3,5):|5-4|=1
  • (4,5):|2-4|=2
  • (2,3):|3-5|=2

因此答案为 7。

数据范围

对于所有测试数据,保证:

  • 1\le n\le 10^6
  • 1\le k\le 10^9
  • 1\le a_i\le 10^9

子任务与评分

本题采用子任务评分,每个子任务包含若干测试点。

子任务分值特殊限制
130 分1\le n\le 3000
230 分1\le n\le 10^5,且 1\le a_i\le 1000
340 分无额外限制

每个子任务只有全部测试点通过才能获得对应分数。

标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 4
通过人数 1
金币数量 3 枚
难度 入门


上一题 下一题