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
bartol3141: 2016-10-21 17:53:22

lower_bound
AC in one go :]

Mihir Saxena: 2016-09-16 00:52:15

Maps and two Pointers!

sas1905: 2016-09-14 23:35:16

Try using maps..:)

square1001: 2016-08-16 03:13:08

No binary Search. It's only sorting and scale-up.

sriraj: 2016-08-15 02:37:39

Easy using maps :D

Abhay: 2016-08-02 19:29:25

WA in python, AC in C++...

codiyapa420: 2016-07-22 21:36:29

ac in 1 go...xtremely easy

visvats_141095: 2016-07-06 05:37:43

similar to OPCPIZZA just one change and AC in 0.05 and AC in 0.04 using fast_io :)

Last edit: 2016-07-06 05:39:55
vineetpratik: 2016-07-04 11:55:23

vector+sort+two_pointers AC in 0.04 sec

at0000001: 2016-06-25 11:51:07

can be done with brute force

Last edit: 2016-06-25 12:26:56

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