← 返回题目列表

Codeforces · 895/B

B. XK 段

中文机器翻译题面 查看原题

当 Vasya 吃完披萨时,课程已经开始了。由于上课迟到,老师建议瓦夏解决一个有趣的问题。 Vasya 有一个数组 a 和整数 x。他应该找到满足 ai ≤ aj 的不同有序索引对 (i, j) 的数量,并且恰好有 k 个整数 y 使得 ai ≤ y ≤ aj 并且 y 可被 x 整除。

在这个问题中,意味着只有当 i 等于 j 时,对 (i, j) 才等于 (j, i)。例如,对 (1, 2) 与 (2, 1) 不同。

输入

第一行包含 3 个整数 n、x、k(1 ≤ n ≤ 105、1 ≤ x ≤ 109、0 ≤ k ≤ 109),其中 n 是数组 a 的大小,x 和 k 是语句中的数字。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) — 数组 a 的元素。

输出

打印一个整数——问题的答案。

示例

输入 #1

4 2 1
1 3 5 7

输出 #1

3

输入 #2

4 2 0
5 3 1 7

输出 #2

4

输入 #3

5 3 1
3 3 3 3 3

输出 #3

25

注意

在第一个示例中,只有三对合适的索引 - (1, 2)、(2, 3)、(3, 4)。

在第二个样本中,有四对合适的索引(1, 1)、(2, 2)、(3, 3)、(4, 4)。

在第三个样本中,每对 (i, j) 都是合适的,所以答案是 5 * 5 = 25。