시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

In C++ division with positive integers always rounds down. Because of this, sometimes when two integers are divided by the same divisor they become equal even though they were originally not equal. For example in C++, 5/4 and 7/4 are both equal to 1, but 5 ≠ 7.

Given a list of nonnegative integers and a divisor, how many pairs of distinct entries in the list are there that give the same result when both are divided by the divisor in C++?

입력

The first line of input contains two integers n (1 ≤ n ≤ 200 000), the number of elements in the list, and d (1 ≤ d ≤ 109), the divisor.

The second line of input contains n integers a1, . . . , an (0 ≤ ai ≤ 109), where ai is the ith element of the list.

출력

Display a single integer indicating the number of distinct pairs of indices (i, j) with 1 ≤ i < j ≤ n such that ai/d = aj/d when using integer division in C++. Note that the numbers in the list are not necessarily distinct (i.e. it is possible that ai = aj for some indices i ≠ j).

예제 입력 1

5 4
4 5 6 7 8

예제 출력 1

6

예제 입력 2

5 1
4 5 6 7 8

예제 출력 2

0

예제 입력 3

6 1
1 2 1 2 1 2

예제 출력 3

6