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

hide comments
killerz: 2012-08-07 02:32:25

Finally AC... simply O(n).. dnt mess it up guys

ɥsǝןǝǝu: 2012-07-21 18:25:51

Got AC...

ken_taiken: 2012-07-15 10:40:30

Pheww AC ! ^^
Costed a lot.

Shubham: 2012-07-11 05:47:14

after trials,I found n>10000 && n<=100000

Last edit: 2012-07-11 06:38:58
spock: 2012-06-16 09:51:21

enjoyed.. :D

ramchand: 2012-06-07 06:52:19

any clues about the input?

ramchand: 2012-06-07 06:51:42

am still getting time limit exceeded error :-(

Darky: 2012-06-04 06:34:31

Finally got AC after many TLE!

Rishi Mukherje: 2012-05-09 06:42:34

same problem in interviewstreet got accepted. My O(n) python solution gets WA here. Why?

Mathan Kumar: 2012-05-03 23:13:18

o(n) is enough using map in c++..


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