While Vasya finished eating his piece of pizza, the lesson has already started. For being late for the lesson, the teacher suggested Vasya to solve one interesting problem. Vasya has an array a and integer x. He should find the number of different ordered pairs of indexes (i, j) such that a_{i} ≤ a_{j} and there are exactly k integers y such that a_{i} ≤ y ≤ a_{j} and y is divisible by x.

In this problem it is meant that pair (i, j) is equal to (j, i) only if i is equal to j. For example pair (1, 2) is not the same as (2, 1).


-----Input-----

The first line contains 3 integers n, x, k (1 ≤ n ≤ 10^5, 1 ≤ x ≤ 10^9, 0 ≤ k ≤ 10^9), where n is the size of the array a and x and k are numbers from the statement.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^9) — the elements of the array a.


-----Output-----

Print one integer — the answer to the problem.


-----Examples-----
Input
4 2 1
1 3 5 7

Output
3

Input
4 2 0
5 3 1 7

Output
4

Input
5 3 1
3 3 3 3 3

Output
25



-----Note-----

In first sample there are only three suitable pairs of indexes — (1, 2), (2, 3), (3, 4).

In second sample there are four suitable pairs of indexes(1, 1), (2, 2), (3, 3), (4, 4).

In third sample every pair (i, j) is suitable, so the answer is 5 * 5 = 25.

Difficulty: interview

Starter code:

Solutions:
import math
import bisect


n, x, k = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
ans = 0

for num in a:
    l = math.ceil(num/x)*x + (k-1)*x
    r = l + x - 1
    l = num if l < num else l
    # print(l, r, bisect.bisect_left(a, l), bisect.bisect_right(a, r), bisect.bisect_right(a, r) - bisect.bisect_left(a, l))
    ans += bisect.bisect_right(a, r) - bisect.bisect_left(a, l)

print(ans)


'''
7 3 2
1 3 5 9 11 16 25
'''

'''
4 2 0
5 3 1 7
'''


n, x, k = list(map(int, input().split()))
array = list(map(int, input().split()))

def next_x(n):
    return ((n+x-1)//x)*x

valcount = {}
for a in array:
    valcount[a] = valcount.get(a, 0) + 1

begs = {}
pairs = 0
for val, count in sorted(valcount.items()):
    if k > 0 or val % x != 0:
        beg = next_x(val)
        begs[beg] = begs.get(beg, 0) + count
        from_ = next_x(val - k*x + 1)
        pairs += count*begs.get(from_, 0)
print(pairs)


import sys
sys.setrecursionlimit(100000000)
# def input(): return sys.stdin.readline()[:-1]
def iin(): return int(input())
def impin(): return list(map(int, input().split()))
def irrin(): return [int(x) for x in input().split()]
def imrin(n): return [int(input()) for _ in range(n)]


def c(n, k):
    if n<k:
        return 0
    s = 1
    for i in range(1, k+1):
        s *= n-i+1
        s //= i
    return s


n, x, k = impin()
arr = irrin()
if k==0:
    trr = {}
    frr = {}
    for a in arr:
        if a%x!=0:
            p = a//x
            if p in trr:
                trr[p] += 1
            else:
                trr[p] = 1
            if a in frr:
                frr[a] += 1
            else:
                frr[a] = 1
    s = 0
    # print(trr)
    for p in trr:
        s += c(trr[p]+1, 2)
        # print(trr[p], s)
    for a in frr:
        s += c(frr[a], 2)
    print(s)
else:
    urr = {}
    lrr = {}
    for a in arr:
        u = (a-1)//x+1
        l = a//x
        # print(a, u, l)
        if u in urr:
            urr[u] += 1
        else:
            urr[u] = 1
        if l in lrr:
            lrr[l] += 1
        else:
            lrr[l] = 1
    s = 0
    for u in urr:
        # print(urr[u])
        l = u+k-1
        # print(u, l)
        if l in lrr:
            s += urr[u]*lrr[l]
    print(s)


# s = 0
# for i in range(n):
#     for j in range(n):
#         if arr[i]>arr[j]:
#             continue
#         c = 0
#         for y in range(arr[i], arr[j]+1):
#             if y%x==0:
#                 c += 1
#         if c==k:
#             print(arr[i], arr[j])
#             s += 1
# print(s)


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2017/11/27 01:27

"""


N, X, K = map(int, input().split())

A = [int(x) for x in input().split()]

# consider special case firstly
if X == 1 and K == 0:
    print(0)
    return

A.sort()

def right(start):
    # find the end for [start, end] has K elements divisible by X
    x = start//X if start%X != 0 else start//X-1
    endmin = max((x+K) * X, start)
    endmax = (x+K+1) * X - 1

    return endmin, endmax

ans = 0
for i, v in enumerate(A):
    rmin, rmax = right(v)
    rl = bisect.bisect_left(A, rmin)
    rr = bisect.bisect_right(A, rmax)
    ans += rr - rl

print(ans)

import bisect
import math

n, x, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
ans = 0
for i in a:
    l = math.ceil(i/x)*x + (k-1)*x
    r = l + x - 1
    if (l < i): l = i  
    else: l = l
    ans += bisect.bisect_right(a, r) - bisect.bisect_left(a, l)
print(ans)

n,x,k=list(map(int,input().split()))
a=list(map(int,input().split()))
from collections import Counter
ans=0
if k!=0:
    dn=Counter()
    un=Counter()
    for i in a:
        dn[i//x]+=1
        un[(i-0.1)//x]+=1
    for item,kol in list(un.items()):
        ans+=kol*dn[item+k]
    print(ans)
else:
    dn = Counter()
    un = Counter()
    s=set()
    for i in a:
        if i%x!=0:
            un[i]+=1
            dn[i//x]+=1
    #print(dn,un,sep='\n')
    for item, kol in list(dn.items()):
        ans += kol*(kol+1)//2
    for item, kol in list(un.items()):
        ans += kol*(kol-1)//2
    print(ans)


n,x,k=list(map(int,input().split()))
a=list(map(int,input().split()))
from collections import Counter
ans=0
if k!=0:
    dn=Counter()
    un=Counter()
    for i in a:
        dn[i//x]+=1
        un[(i-0.1)//x]+=1
    for item,kol in list(un.items()):
        ans+=kol*dn[item+k]
    print(ans)
else:
    dn = Counter()
    un = Counter()
    s=set()
    for i in a:
        if i%x!=0:
            un[i]+=1
            dn[i//x]+=1
    #print(dn,un,sep='\n')
    for kol in list(dn.values()):
        ans += kol*(kol+1)//2
    for kol in list(un.values()):
        ans += kol*(kol-1)//2
    print(ans)


import sys
from bisect import *
import math

N,X,K = list(map(int, input().split()))
p = sorted(list(map(int, input().split())))

def get(l, r):
	return (r//X) - (l-1)//X

p = sorted(p)
mp = {}
n = len(p)

for i in range(n):
	if p[i] in mp:
		continue
	else:
		mp[p[i]] = i
x = 5
ans = 0
mx = 0

for i in range(0,n):
	x = p[i]
	a = x//X
	mn = 0
	mx = 0

	if x % X == 0 :
		mn = x + (K-1)*X
		mx = mn + X-1
	else:
		mn =(x//X)*X + (K)*X
		mx = mn + X-1
	if K == 0:
		if x%X == 0 :
			continue
		mn = x
		mx = (x//X)*X+X-1
	#print(x,mn,mx)
	if mn > mx:
		continue
	ans = ans + bisect_right(p,mx) - bisect_left(p,mn)

print(ans)


from bisect import bisect_left
R=lambda:list(map(int,input().split()))
n,x,k=R()
a=sorted(R())
cnt=0
for u in a:
    l=((u+x-1)//x+k-1)*x
    cnt+=bisect_left(a,l+x)-bisect_left(a,max(u,l))
print(cnt)


from bisect import bisect_left
R=lambda:map(int,input().split())
n,m,k=R()
a=sorted(R())
s=0
for i in a:
    l = ((i - 1) // m + k) * m
    s+=bisect_left(a,l+m)-bisect_left(a,max(i,l))
print(s)

from bisect import bisect_left
R=lambda:list(map(int,input().split()))
n,x,k=R()
a=sorted(R())
s=0
for u in a:
    l=((u-1)//x+k)*x
    s+=bisect_left(a,l+x)-bisect_left(a,max(u,l))
print(s)


from bisect import bisect_left
R=lambda:list(map(int,input().split()))
n,x,k=R()
a=sorted(R())
z=list(zip(a,(((u-1)//x+k)*x for u in a)))
print(sum(bisect_left(a,l+x)-bisect_left(a,max(u,l)) for u,l in z))


from bisect import bisect_left
R=lambda:list(map(int,input().split()))
n,x,k=R()
a=sorted(R())
z=((u,((u-1)//x+k)*x) for u in a)
print(sum(bisect_left(a,l+x)-bisect_left(a,max(u,l)) for u,l in z))


from bisect import bisect_left
R=lambda:list(map(int,input().split()))
n,x,k=R()
a=sorted(R())
b=(((u-1)//x+k)*x for u in a)
print(sum(bisect_left(a,l+x)-bisect_left(a,max(u,l)) for u,l in zip(a,b)))


from bisect import bisect_left
R=lambda:list(map(int,input().split()))
n,x,k=R()
a=sorted(R())
print(sum(bisect_left(a,l+x)-bisect_left(a,max(u,l)) for u,l in ((u,((u-1)//x+k)*x) for u in a)))


from bisect import bisect_left, bisect_right

n, x, k = [int(i) for i in input().split(' ')]
ar = sorted([int(i) for i in input().split(' ')])

lk, nk = -1, 0

n_tup = 0

if x != 1 or k != 0:
    for i in range(len(ar)):
        nk = ar[i]
        if lk != nk:
            xf = (k + (ar[i] - 1) // x)
            lo = bisect_left(ar, ar[i])
            # Find rightmost value less than xf*x
            lt = bisect_left(ar, (xf+1)*x, lo)
            # Find leftmost value greater than (xf+1)*x
            gt = bisect_right(ar, xf*x-1, lo)
        n_tup += lt - gt
        lk = nk

print(n_tup)

from bisect import bisect_left as b
R=lambda:list(map(int,input().split()))
n,x,k=R()
a=sorted(R())
print(sum(b(a,l+x)-b(a,max(u,l)) for u,l in ((u,((u-1)//x+k)*x) for u in a)))


from bisect import bisect_left

n, x, k = list(map(int, input().split()))
arr = sorted(list(map(int, input().split())))

ranges = []
for a in arr:
    if k == 0:
        a1 = (((a - 1) // x) + 1) * x
        l = a
        r = a1 + x * (k - 1) + x
    else:
        a1 = (((a - 1) // x) + 1) * x
        l = a1 + x * (k - 1)
        r = a1 + x * (k - 1) + x
    ranges.append((min(l, r), max(l, r)))
res = 0

# print(arr)
# print(ranges)

for l, r in ranges:
    left_index = bisect_left(arr, l)
    right_index = bisect_left(arr, r)
    res += right_index - left_index
    # print(left_index, right_index)

print(res)


n, x, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

a.sort()

ans = 0
s, t = 0, 0
for j in range(n):
	cur = ((a[j] // x) - k) * x
	
	while s < n and a[s] <= min(cur,a[j]):
		s += 1
		
	while t < n and a[t] <= min(cur + x, a[j]):
		t += 1
	
	ans += (t-s)
	
print(ans)

import bisect
def lower_bound(A, x):
    low = 0
    high = len(A)
    while(low < high):
        mid = (low + high) // 2
        if(int(A[mid]) < x):
            low = mid + 1
        else:
            high = mid
    return low

def upper_bound(A, x):
    low = 0
    high = len(A)
    while(low < high):
        mid = (low + high) // 2
        if(int(A[mid]) <= x):
            low = mid + 1
        else:
            high = mid
    return low
line = input().split()
n = int(line[0])
x = int(line[1])
k = int(line[2])
a = [int(x) for x in input().split()]
a.sort()

ans = 0
for i in a:
    left = (i + x - 1) // x * x
    right = left + x * k - 1
    left = left + (k - 1) * x
    left = max(left, i)
    ans = ans + bisect.bisect_right(a, right) - bisect.bisect_left(a, left)
    # print(left, right, ans)
print(ans)



from bisect import bisect_left as b
f = lambda: map(int, input().split())
n, x, k = f()
s, t = 0, sorted(f())
p = [(q, ((q - 1) // x + k) * x) for q in t]
for q, d in p: s += b(t, d + x) - b(t, max(q, d))
print(s)

f = lambda: map(int, input().split())
n, x, k = f()
t = sorted(f())
s = i = j = 0
for y in t:
    d = (y // x - k) * x
    while i < n and t[i] <= min(d, y): i += 1
    while j < n and t[j] <= min(d + x, y): j += 1
    s += j - i
print(s)