| Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 1 сек | |
| Входной файл: | game.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | game.out | |||
| Максимальный балл: | 100 |
Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал A баллов, второй — B, а третий C, то говорят, что игра закончилась со счетом A:B:C.
Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в K раз.
После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из N карточек, на которых написаны числа x1, x2, …, xN. Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.
Требуется написать программу, которая по числу K и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.
Первая строка входного файла содержит два целых числа: N и K. Вторая строка входного файла содержит N целых чисел x1, x2, …, xN.
Выходной файл должен содержать одно целое число — искомое количество различных вариантов счета.
3 ≤ N ≤ 100 000; 1 ≤ K ≤ 109; 1 ≤ xi ≤ 109
В приведенном примере Андрей сможет показать следующие варианты счета: 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.
3 ≤ N ≤ 100 000; K = 1; 1 ≤ xi ≤ 100 000
3 ≤ N ≤ 100; 1 ≤ K ≤ 100; 1 ≤ xi ≤ 100
3 ≤ N ≤ 100 000; 1 ≤ K ≤ 109; 1 ≤ xi ≤ 109; все xi различны
3 ≤ N ≤ 100 000; 1 ≤ K ≤ 109; 1 ≤ xi ≤ 109
По запросу сообщается результат окончательной проверки на каждом тесте.
| № | Входной файл (game.in) |
Выходной файл (game.out) |
|---|---|---|
| 1 | |
|