A Sumo wrestling championship is scheduled to be held this winter in the HackerCity where N wrestlers from different parts of the world are going to participate. The rules state that two wrestlers can fight against each other if and only if the difference in their height is less than or equal to K, 

(i.e) wrestler A and wrestler B can fight if and only if |height(A)-height(B)|<=K.  

Given an array H[], where H[i] represents the height of the i^{th} fighter, for a given l, r where 0 <= l <= r < N, can you count the number of pairs of fighters between l and r (both inclusive) who qualify to play a game?

Input Format 

The first line contains an integer N and K  separated by a single space representing the number of Sumo wrestlers who are going to participate and the height difference K. 

The second line contains N integers separated by a single space, representing their heights H[0] H[1] ... H[N - 1]. 

The third line contains Q, the number of queries. This is followed by Q lines each having two integers l and r separated by a space.  

Output Format 

For each query Q, output the corresponding value of the number of pairs of fighters for whom the absolute difference of height is not greater that K.  

Constraints 

1 <= N <= 100000 

0 <= K <= $10^{9} $

0 <= H[i] <= $10^{9} $

1 <= Q <= 100000 

0 <= l <= r < N  

Sample Input

5 2
1 3 4 3 0
3
0 1
1 3
0 4

Sample Output  

1
3
6

Explanation 

Query #0: Between 0 and 1 we have i,j as (0,1) and |H[0]-H[1]|=2 therefore output is 1. 

Query #1: The pairs (H[1],H[2]) (H[1],H[3]) and (H[2],H[3]) are the pairs such that |H[i]-H[j]| <=2. Hence output is 3. 

Query #2: Apart from those in Query #1, we have (H[0],H[1]), (H[0], H[3]), (H[0], H[4]), hence 6.  

Timelimits

Timelimits are given here

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
(N, K) = map(int, input().split(' '))
heights = list(map(int, input().split(' ')))
assert N == len(heights)
fights = [[0] for i in range(N)]
for (sumo1, height1) in enumerate(heights):
	num_fights = 0
	for sumo2 in range(sumo1 + 1, N):
		if abs(height1 - heights[sumo2]) <= K:
			num_fights += 1
		fights[sumo1].append(num_fights)

def query(l, r):
	return sum((fights[sumo][r - sumo] for sumo in range(l, r)))

def run_queries():
	num_queries = int(input())
	for i in range(num_queries):
		if i:
			print('')
		(l, r) = map(int, input().split(' '))
		print(query(l, r), end='')
run_queries()


(N, K) = [int(x) for x in input().split()]
heights = [int(x) for x in input().split()]
global memo
memo = {}

def compareOne(x, y):
	if abs(heights[x] - heights[y]) > K:
		res = 0
	else:
		res = 1
	return res

def compareAll(x, y):
	if (x, y) in memo:
		return memo[x, y]
	res = 0
	for i in range(x + 1, y + 1):
		res += compareOne(x, i)
	if y > x:
		res += compareAll(x + 1, y)
	memo[x, y] = res
	return res
Q = int(input().strip())
for test in range(Q):
	(x, y) = [int(x) for x in input().split()]
	print(compareAll(x, y))


import bisect
(n, k) = map(int, input().strip().split())
H = list(map(int, input().strip().split()))
assert len(H) == n
t = int(input().strip())
for _ in range(t):
	(l, r) = map(int, input().strip().split())
	h = sorted(H[l:r + 1])
	p = 0
	for (i, x) in enumerate(h):
		p += bisect.bisect_right(h, x + k, i) - i - 1
	print(p)