P1296 Cows' Whispers

In your cattle farm, all cows are kept in a row of stalls arranged along a straight line. There are $n$ cows, and the position of the $i$-th cow on the line is represented by an integer coordinate $p_i(0\le p_i \le 10^8)$. On boring days, cows often share gossip from their own stalls. Each cow speaks with the same loudness, but due to sound attenuation, a cow’s voice can only be heard by cows within a distance no greater than $d(0 \le d \le 10^4)$. In this case, the pair of cows is said to be able to communicate with each other. Given all cows’ positions and the maximum propagation distance $d$, please write a program to compute how many pairs of cows in your farm can communicate.

The first line contains two integers $n,d$. The second line contains $n$ integers, each being a coordinate $p_i$, describing a cow’s position on the line.

A single integer, the number of pairs of cows in the farm that can communicate.

Constraints - For $40\%$ of the data, $1 \leq n \leq 10^3$. - For $100\%$ of the data, $1 \leq n \leq 10^6$. Translated by ChatGPT 5