Дистанционный практикум по программированию

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал a баллов, второй — b, а третий c, то говорят, что игра закончилась со счетом a:b:c.

Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в k раз.

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа x₁, x₂, …, x_n. Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

Требуется написать программу, которая по числу k и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.

Формат входного файла

Первая строка входного файла содержит два целых числа: n и k (3 ≤ n ≤ 100 000, 1 ≤ k ≤ 10⁹).

Вторая строка входного файла содержит n целых чисел x₁, x₂, …, x_n (1 ≤ x_i ≤ 10⁹).

Формат выходного файла

Выходной файл должен содержать одно целое число — искомое количество различных вариантов счета.

Пример входных и выходных файлов

Входные данные	Выходные данные
5 2 1 1 2 2 3	9

Пояснение к примеру

В приведенном примере Андрей сможет показать следующие варианты счета: 1:1:2, 1:2:1, 2:1:1, 1:2:2, 2:1:2, 2:2:1, 2:2:3, 2:3:2, 3:2:2. Другие тройки чисел, которые можно составить с использованием имеющихся карточек, не удовлетворяют заданному условию, что баллы любых двух игроков различаются не более чем в k = 2 раза.

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только каких-либо из подзадач 1 и 3.

Подзадача 1 (15 баллов)

3 ≤ n ≤ 100 000, k = 1, 1 ≤ x_i ≤ 100 000

Подзадача 2 (23 балла)

3 ≤ n ≤ 100, 1 ≤ k ≤ 100, 1 ≤ x ≤ 100

Подзадача 3 (30 баллов)

3 ≤ n ≤ 100 000, 1 ≤ k ≤ 10⁹, 1 ≤ x_i ≤ 10⁹, все x_i различны.

Подзадача 4 (32 балла)

3 ≤ n ≤ 100 000, 1 ≤ k ≤ 10⁹, 1 ≤ x ≤ 10⁹

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.