Слишком близкие результаты

На школьных соревнованиях по бегу судья хочет понять, сколько пар участников показали «почти одинаковый» результат.

Результат каждого участника — целое число (например, время в миллисекундах). Пара участников считается «почти одинаковой», если разница их результатов не больше D.

Посчитайте, сколько существует пар участников (i, j), где i < j, таких что |a[i] - a[j]| ≤ D.

Важно: значения и ответ могут не помещаться в 32-битный тип (как на олимпиадах), используйте 64-битную арифметику. В Python это уже учтено.

Формат ввода

В первой строке записаны два целых числа n и D. Во второй строке записаны n целых чисел a1, a2, ..., an — результаты участников.

Формат вывода

Выведите одно целое число — количество пар (i, j), i < j, для которых |ai - aj| ≤ D.

Ограничения

• 2 ≤ n ≤ 35000
• 0 ≤ D ≤ 2_000_000_000
• -1_000_000_000 ≤ ai ≤ 1_000_000_000

Пример

Ввод:

5 3
1 2 10 4 7

Вывод:

5

Подходящие пары по значениям: (1,2), (1,4), (2,4), (4,7), (7,10).

Ключевое наблюдение: условие |a[i] - a[j]| ≤ D неудобно в исходном порядке, но после сортировки всё упрощается. Если a отсортирован, то для i < j разность просто a[j] - a[i] (она уже неотрицательная), и для фиксированного i подходят подряд идущие j: как только разница стала больше D, дальше (при большем j) она уже не уменьшится.

Здесь работает приём «два указателя» (скользящее окно): правая граница j никогда не двигается назад, поэтому общий проход получается линейным.

План:

• Отсортировать массив a.
• Завести j = 0 и ans = 0.
• Для каждого i слева:
• сделать j = max(j, i+1).
• пока j < n и a[j] - a[i] ≤ D, увеличивать j.
• все индексы i+1 ... j-1 дают подходящие пары с i, добавить их количество: ans += (j - i - 1).
• Вывести ans (в Python тип int уже «64-бит+»).

Сложность: сортировка O(n log n) и один линейный проход O(n), память O(1) сверх массива.

Частая ошибка: сбрасывать j в i+1 на каждом шаге без max(...) или двигать j назад — это легко превращает решение в O(n^2).