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
panjiara_01: 2018-02-09 01:13:51

0.04 using binary search :)

v_pp_27: 2018-02-05 16:05:53

0.07 using nlogn binary search....!

sophozaar: 2018-02-04 18:16:52

0.03 sec : sorting + 2-pointer

sirjan13: 2017-12-19 19:35:58

sorting +2pointer->AC :)

avik26091998: 2017-12-03 16:45:23

0.02s Binary search!!!

algolover: 2017-11-08 18:57:38

binarysearch 0.03 AC

frozen7: 2017-10-13 20:22:55

simple binary search my 50th .. :-) :-)

perfectgod: 2017-07-31 15:01:15

jawad-cs unordered map can take o(n) worst case time
O(1) worst case time which we are given is actually amortised time complexity
search google for more

anurag_tangri: 2017-06-22 21:23:33

AC IN ONE GO:)

ak_cruiser: 2017-06-18 02:11:01

recursive binary search might give TLE ...try to use iterative approach..passed in 0.04 ,using unordered_map to keep it more simple


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