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
hrishabh: 2015-08-02 20:51:14

binary search..;)

Vaporeon: 2015-07-27 19:52:08

easy :)

Anurag Sharma: 2015-07-25 19:05:58

Merge sort + binary search =AC in one go...... should be considered as tutorial problem.... only for dummies :P

Varun Gambhir: 2015-07-20 22:38:00

STL rocks! :)

SangKuan: 2015-06-29 03:51:53

ok,i knowed how to do in O(n)...

SangKuan: 2015-06-29 03:48:51

O((n+1)logn) ac.who can tell me how to do O(n)?

PRIBAN91: 2015-06-09 19:21:25

Java users be very careful! Try to write your own parsing class with less buffer space. Nice problem to judge your skill and depth in the knowledge of Java.

Rahul Jain: 2015-06-04 20:01:56

no need of binary search.. sorting+one scan of array is sufficient. i.e O(nlogn + n)

harshit sharma: 2015-06-03 10:30:24

easy binary search.. :)
weak test cases...

kartikay singh: 2015-05-19 08:32:53

merge sort+binary search ==> AC:)


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