Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал \(a\) баллов, второй
— \(b\), а третий \(c\), то говорят, что игра закончилась со счетом \(a:b:c\).
Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в \(k\) раз.
После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа \(x_1, x_2, …, x_n\). Чтобы выяснить, насколько он готов к чемпионату, Андрей
хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.
Требуется написать программу, которая по числу \(k\) и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.
Выходные данные
Выходной файл должен содержать одно целое число — искомое количество различных вариантов счета.
Пояснение к примеру
В приведенном примере Андрей сможет показать следующие варианты счета: 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 (15 баллов)
\(3 \le n \le 100 000, k = 1, 1 \le x_i \le 100 000\)
Подзадача 2 (23 балла)
\(3 \le n \le 100, k \le 100, 1 \le x_i \le 100\)
Подзадача 3 (30 баллов)
\(3 \le n \le 100 000, k \le 10^9 \le x_i \le 10^9\), все \(x_i\) различны
Подзадача 4 (32 балла)
\(3 \le n \le 100 000, k \le 10^9 \le x_i \le 10^9\)