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
2012-05-03 23:13:18 Mathan Kumar
o(n) is enough using map in c++..
2012-04-22 03:06:45 PANKAJ SAINI
what is the limit of n??
2012-03-14 14:38:48 arjun
O(nlogn) +O(n)
2012-02-06 21:10:13 张翼德
read question twice and google wat predominantly means haha:)
2012-01-15 15:34:27 PubLic_AvenGeR
nlogn passes with ease....Good ques anyways..... :)
2012-01-05 12:46:11 BOND
just think how to use increasing sequence ...
2011-12-31 15:40:47 Aradhya
plz tell the range of n...
2011-12-31 12:37:01 Allada Revanth Kumar
seems very easy problem... but could not understand why i am getting TLE.. please help
2011-12-28 18:31:30 bristy
@admin_
can a no. repeat?
2011-12-23 06:45:26 Anurag Aggarwal
@author
At least correct the input format correctly.
Problem says that that 2nd line will contain all the numbers but 2nd line is not a single line it is a combination of n line

@Mitch Schwartz
Thanks..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.