Пока Вася доедал свой кусок пиццы, пара уже началась. За опоздание на пару преподаватель предложил Васе поразмыслить над одной интересной задачей. Васе даны массив a и целое число x. Ему необходимо вычислить количество различных пар индексов (i, j) для которых ai ≤ aj и существует ровно k целых чисел y таких, что ai ≤ y ≤ aj и при этом y делится на x без остатка.
В данной задаче считается, что пара (i, j) не равна паре (j, i), если j не равно i, то есть (1, 2) и (2, 1) это две разные пары.
Выходные данные
Выведите одно целое число — ответ на задачу.
Примечание
В первом тесте подходят только следующие пары индексов: (1, 2), (2, 3), (3, 4).
Во втором тесте подходят пары индексов (1, 1), (2, 2), (3, 3), (4, 4).
В третьем тесте подходит любая пара индексов (i, j). Поэтому ответ равен 5 * 5 = 25.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2 1
1 3 5 7
|
3
|
|
2
|
4 2 0
5 3 1 7
|
4
|
|
3
|
5 3 1
3 3 3 3 3
|
25
|