Тройка точек $$$i$$$, $$$j$$$ и $$$k$$$ на координатной прямой считается красивой, если $$$i < j < k$$$ и $$$k - i \le d$$$.
Вам задано множество точек на координатной прямой, изначально пустое. Вам нужно обрабатывать запросы трех типов:
В первой строке заданы два целых числа $$$q$$$ и $$$d$$$ ($$$1 \le q, d \le 2 \cdot 10^5$$$) — количество запросов и параметр, по которому определяется, является ли тройка красивой.
Во второй строке заданы $$$q$$$ целых чисел $$$a_1, a_2, \dots, a_q$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$). Число $$$a_i$$$ обозначает $$$i$$$-й запрос следующим образом:
Для каждого запроса выведите одно целое число — количество красивых троек после обработки запроса.
7 5 8 5 3 2 1 5 6
0 0 1 2 5 1 5
Название |
---|