HACKRNDM - Hacking the random number generator

You recently wrote a random number generator code for a web application and now you notice that some cracker has cracked it. It now gives numbers at a difference of some given value k more predominantly. You being a hacker decide to write a code that will take in n numbers as input and a value k and find the total number of pairs of numbers whose absolute difference is equal to k, in order to assist you in your random number generator testing.

NOTE: All values fit in the range of a signed integer, n, k>=1

Input

1st line contains n & k.
2nd line contains n numbers of the set. All the n numbers are assured to be distinct.

(Edited: n <= 10^5)

Output

One integer saying the no of pairs of numbers that have a diff k.

Example

Input:
5 2
1 5 3 4 2 Output: 3

Added by:vijay
Date:2011-10-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2011-10-19 05:06:57 biQar
what is the value for "n" ? & what is the type of language ?
2011-10-19 05:06:57 Mitch Schwartz
From experimentation, I find that the "second line" of input actually spans n lines; where you would expect ' ', there is instead '\n'. Also, it is safe to assume n > 1 and k > 0.

Furthermore, all numbers are non-negative.

Last edit: 2011-10-16 21:18:36
2011-10-19 05:06:57 R@ja.... -[^_^]-
is O(nlogn) acceptable..
2011-10-19 05:06:57 [Retired]
Nice problems...;)

Last edit: 2011-10-16 11:24:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.