{"raw_statement":[{"iden":"statement","content":"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_.\n\nIn 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)."},{"iden":"input","content":"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.\n\nThe second line contains _n_ integers _a__i_ (1 ≤ _a__i_ ≤ 109) — the elements of the array _a_."},{"iden":"output","content":"Print one integer — the answer to the problem."},{"iden":"examples","content":"Input\n\n4 2 1\n1 3 5 7\n\nOutput\n\n3\n\nInput\n\n4 2 0\n5 3 1 7\n\nOutput\n\n4\n\nInput\n\n5 3 1\n3 3 3 3 3\n\nOutput\n\n25"},{"iden":"note","content":"In first sample there are only three suitable pairs of indexes — (1, 2), (2, 3), (3, 4).\n\nIn second sample there are four suitable pairs of indexes(1, 1), (2, 2), (3, 3), (4, 4).\n\nIn third sample every pair (_i_, _j_) is suitable, so the answer is 5 * 5 = 25."}],"translated_statement":[{"iden":"statement","content":"当 Vasya 吃完他的披萨时，课程已经开始了。由于迟到，老师让 Vasya 解决一个有趣的问题。Vasya 有一个数组 #cf_span[a] 和一个整数 #cf_span[x]。他需要找出满足以下条件的不同有序下标对 #cf_span[(i, j)] 的数量：#cf_span[ai ≤ aj]，且恰好存在 #cf_span[k] 个整数 #cf_span[y] 满足 #cf_span[ai ≤ y ≤ aj] 且 #cf_span[y] 能被 #cf_span[x] 整除。\n\n在本题中，下标对 #cf_span[(i, j)] 仅当 #cf_span[i] 等于 #cf_span[j] 时才与 #cf_span[(j, i)] 相等。例如，下标对 #cf_span[(1, 2)] 不等于 #cf_span[(2, 1)]。\n\n第一行包含三个整数 #cf_span[n, x, k] (#cf_span[1 ≤ n ≤ 105, 1 ≤ x ≤ 109, 0 ≤ k ≤ 109])，其中 #cf_span[n] 是数组 #cf_span[a] 的大小，#cf_span[x] 和 #cf_span[k] 是题目中给出的数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 109]) —— 数组 #cf_span[a] 的元素。\n\n请输出一个整数 —— 问题的答案。\n\n在第一个样例中，只有三个合适的下标对 —— #cf_span[(1, 2), (2, 3), (3, 4)]。\n\n在第二个样例中，有四个合适的下标对 #cf_span[(1, 1), (2, 2), (3, 3), (4, 4)]。\n\n在第三个样例中，每对 #cf_span[(i, j)] 都合适，因此答案是 #cf_span[5 * 5 = 25]。"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n, x, k] (#cf_span[1 ≤ n ≤ 105, 1 ≤ x ≤ 109, 0 ≤ k ≤ 109])，其中 #cf_span[n] 是数组 #cf_span[a] 的大小，#cf_span[x] 和 #cf_span[k] 是题目中给出的数。第二行包含 #cf_span[n] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 109]) —— 数组 #cf_span[a] 的元素。"},{"iden":"output","content":"请输出一个整数 —— 问题的答案。"},{"iden":"examples","content":"输入\n4 2 1\n1 3 5 7\n输出\n3\n\n输入\n4 2 0\n5 3 1 7\n输出\n4\n\n输入\n5 3 1\n3 3 3 3 3\n输出\n25"},{"iden":"note","content":"在第一个样例中，只有三个合适的下标对 —— #cf_span[(1, 2), (2, 3), (3, 4)]。在第二个样例中，有四个合适的下标对 #cf_span[(1, 1), (2, 2), (3, 3), (4, 4)]。在第三个样例中，每对 #cf_span[(i, j)] 都合适，因此答案是 #cf_span[5 * 5 = 25]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, x, k \\in \\mathbb{Z} $ be given integers.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in \\mathbb{Z} $ for all $ i \\in \\{1, \\dots, n\\} $.  \n\nFor any ordered pair $ (i, j) \\in \\{1, \\dots, n\\}^2 $, define the interval $ [a_i, a_j] = \\{ y \\in \\mathbb{Z} \\mid a_i \\leq y \\leq a_j \\} $.  \nLet $ f(i, j) = \\left| \\left\\{ y \\in [a_i, a_j] \\mid y \\equiv 0 \\pmod{x} \\right\\} \\right| $, i.e., the count of multiples of $ x $ in the closed interval from $ a_i $ to $ a_j $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq x \\leq 10^9 $  \n3. $ 0 \\leq k \\leq 10^9 $  \n4. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n5. Only pairs $ (i, j) $ with $ a_i \\leq a_j $ are considered.\n\n**Objective**  \nCompute the number of ordered pairs $ (i, j) $ such that:  \n- $ a_i \\leq a_j $, and  \n- $ f(i, j) = k $.  \n\nThat is, compute:  \n$$\n\\left| \\left\\{ (i, j) \\in \\{1, \\dots, n\\}^2 \\mid a_i \\leq a_j \\text{ and } \\left| \\left\\{ y \\in [a_i, a_j] : x \\mid y \\right\\} \\right| = k \\right\\} \\right|\n$$","simple_statement":null,"has_page_source":false}