当 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。