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
2015-08-02 20:51:14 hrishabh
binary search..;)
2015-07-27 19:52:08 Vaporeon
easy :)
2015-07-25 19:05:58 Anurag Sharma
Merge sort + binary search =AC in one go...... should be considered as tutorial problem.... only for dummies :P
2015-07-20 22:38:00 Varun Gambhir
STL rocks! :)
2015-06-29 03:51:53 SangKuan
ok,i knowed how to do in O(n)...
2015-06-29 03:48:51 SangKuan
O((n+1)logn) ac.who can tell me how to do O(n)?
2015-06-09 19:21:25 PRIBAN91
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.
2015-06-04 20:01:56 Rahul Jain
no need of binary search.. sorting+one scan of array is sufficient. i.e O(nlogn + n)
2015-06-03 10:30:24 harshit sharma
easy binary search.. :)
weak test cases...
2015-05-19 08:32:53 kartikay singh
merge sort+binary search ==> AC:)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.