|
Спонтанная покупка
(Время: 1 сек. Память: 32 Мб Сложность: 30%)
Маркетологи знают, что в супермаркетах покупатель сначала ведёт себя рационально, а в конце срывается на спонтанную покупку у кассы.
Вы анализируете чек из трёх разных товаров, купленных ровно в том порядке, в котором они написаны в чеке. Всего в магазине
N товаров, каждый i-й товар имеет цену Ki рублей.
Покупатель выбирает товар по цепочке:
- Первый товар – любой;
- Второй товар стоит примерно столько же, сколько первый: разница их цен не превышает T;
- Третий товар резко отличается по цене от первого; разница их цен строго больше T.
Сколько существует способов собрать такой чек из товаров, имеющихся в магазине?
Входные данные
В первой строке входного файла INPUT.TXT записано натуральное число N – количество товаров. Во второй строке записано натуральное число T – разность цен (3 ≤ N ≤ 105, 0 ≤ T ≤ 109).
В следующих строках записаны N натуральных чисел Ki по одному в строке, i-е по счёту число равно стоимости i-го товара (1 ≤ Ki ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – ответ на задачу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
2
4
5
2
2 | 6 |
Пояснение к примеру
В тестовом примере для сборки чека, который подходит маркетологам, можно использовать следующие товары:
- второй, первый и третий товары;
- второй, первый и четвёртый товары;
- третий, четвёртый и второй товары;
- третий, первый и второй товары;
- четвёртый, третий и второй товары;
- четвёртый, первый и второй товары.
Система оценки
Решения, правильно работающие при N ≤ 100, будут оцениваться в 20 баллов.
Решения, правильно работающие при N ≤ 1000, будут оцениваться в 30 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
