Совпали по шагам

В школьном чате ребята сравнивают, сколько шагов за день показал их браслет. Два человека считают свои результаты «похожими», если разница между числом шагов не больше, чем d.

Посчитайте, сколько существует неупорядоченных пар учеников (то есть пар (i, j) с i < j), у которых результаты похожи.

Важно: ответ может не поместиться в 32-битный тип, используйте 64-битные целые (в Python это не проблема).

Формат ввода

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

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

Выведите одно целое число — количество пар (i, j), где i < j и |a[i] − a[j]| ≤ d.

Ограничения

• 1 ≤ n ≤ 12000
• 0 ≤ d ≤ 1 000 000
• 0 ≤ a[i] ≤ 1 000 000

Пример

Ввод:

5 2
1 3 5 4 2

Вывод:

7

Ключевое наблюдение: если отсортировать массив a, то для любых l < r условие |a[l] - a[r]| <= d превращается в просто a[r] - a[l] <= d (модуль не нужен, потому что a[r] >= a[l]). Тогда все подходящие пары для фиксированного l образуют непрерывный отрезок по r.

Приём: два указателя. Двигаем правый указатель только вперёд, поэтому суммарно он сделает не больше n шагов — получается линейный проход после сортировки.

План:

• Считай n, d и массив, отсортируй его.
• Заведи ans = 0 и указатель r = 0.
• Для каждого l от 0 до n-1:
• Убедись, что r >= l+1 (иначе поставь r = l+1).
• Пока r < n и a[r] - a[l] <= d, увеличивай r.
• Теперь r — первый индекс, где условие ломается, значит подходящих j ровно r - l - 1.

Добавь к ответу: ans += (r - l - 1).

Мини-сниппет формулы подсчёта: ans += r - l - 1

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

Частая ошибка: сбрасывать r назад для каждого l (тогда выйдет O(n^2)), или посчитать пары дважды. Здесь каждая пара учитывается ровно один раз, потому что фиксируем левый индекс и берём только j > l.