CF895B.XK Segments

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).

当瓦西娅吃完他的那块披萨时，课程已经开始了。由于上课迟到，老师让瓦西娅解决一个有趣的问题。瓦西娅有一个数组 $a$ 和一个整数 $x$。他需要找出满足以下条件的不同有序索引对 $(i,\,j)$ 的个数：$a_i \leq a_j$，且在区间 $[a_i,\,a_j]$ 中恰好有 $k$ 个整数 $y$ 满足 $y$ 被 $x$ 整除。

本题中，仅当 $i = j$ 时，索引对 $(i,\,j)$ 才被认为等于 $(j,\,i)$。例如，$(1,\,2)$ 与 $(2,\,1)$ 被视为不同的对。

The first line contains 3 integers n, x, k (1 ≤ n ≤ 105, 1 ≤ x ≤ 109, 0 ≤ k ≤ 109), 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 ≤ 109) — the elements of the array a.

第一行包含 3 个整数 $n$、$x$、$k$（$1 \le n \le 10^5$，$1 \le x \le 10^9$，$0 \le k \le 10^9$），其中 $n$ 是数组 $a$ 的大小，$x$ 和 $k$ 是题目描述中给出的数。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）—— 数组 $a$ 的元素。

Print one integer — the answer to the problem.

输出一个整数——该问题的答案。

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.

第一个样例中仅有三对合适的下标：$(1,\,2),\,(2,\,3),\,(3,\,4)$。

第二个样例中有四对合适的下标：$(1,\,1),\,(2,\,2),\,(3,\,3),\,(4,\,4)$。

第三个样例中，每一对 $(i,\,j)$ 均合适，因此答案为 $5\,\times\,5\,=\,25$。