Tổng chênh lệch gần (Sum of Nearby Differences)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho $N$ số nguyên $A_1,A_2,\ldots,A_N$ và số nguyên không âm $D$. Một cặp chỉ số không thứ tự $\{i,j\}$ với $i<j$ được gọi là gần nếu

$$|A_i-A_j|\le D.$$

Đóng góp của cặp gần $\{i,j\}$ bằng $|A_i-A_j|$. Hãy tính

$$T=\sum_{1\le i<j\le N,\ |A_i-A_j|\le D} |A_i-A_j|.$$

Input

• Dòng đầu chứa hai số nguyên $N,D$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In một số nguyên duy nhất là $T$.

Subtask

• Subtask 1 (35%): $1\le N\le 2000$, $0\le D,A_i\le 10^6$.
• Subtask 2 (25%): $1\le N\le 2\cdot 10^5$, $D=10^6$, $0\le A_i\le 10^6$.
• Subtask 3 (40%): $1\le N\le 2\cdot 10^5$, $0\le D,A_i\le 10^6$.

Ví dụ

Ví dụ 1

Input

5 3
1 4 6 7 10

Output

12

Giải thích

Các hiệu hợp lệ là $3,2,3,1,3$, tương ứng với các cặp giá trị $(1,4),(4,6),(4,7),(6,7),(7,10)$. Tổng bằng $12$.

Ví dụ 2

Input

4 0
5 5 5 5

Output

0

Giải thích

Chỉ các cặp có hai giá trị bằng nhau là gần, nhưng mọi đóng góp đều bằng $0$.