C. Скользящие окна
ограничение по времени на тест
2 с
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим массив чисел $$$b_1, \dots, b_m$$$. Скользящими окнами длины $$$k$$$ ($$$k \le m$$$) на этом массиве называются все подотрезки длины $$$k$$$, то есть отрезки $$$[b_1, \dots, b_k]$$$, $$$[b_2, \dots, b_{k + 1}]$$$, $$$\dots,$$$ $$$[b_{m-k+1}, \dots, b_m]$$$.

Дан массив чисел $$$a_1, \dots, a_n$$$ длины $$$n$$$. Ответьте на $$$q$$$ запросов следующего вида про этот массив: для заданных $$$l$$$, $$$r$$$, $$$k$$$ найти сумму минимумов на скользящих окнах длины $$$k$$$ на подотрезке $$$[a_l, \dots, a_r]$$$.

Входные данные

В первой строке входных данных даны два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 100\,000$$$) — длина массива и количество запросов.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — значения чисел в массиве.

В следующих $$$q$$$ строках даны запросы. В $$$i$$$-й из них даны три целых числа $$$l_i$$$, $$$r_i$$$ и $$$k_i$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le k \le r - l + 1$$$) — левая и правая границы отрезков и длина скользящего окна в $$$i$$$-м запросе.

Выходные данные

Выведите $$$q$$$ строк с ответами на запросы. В $$$i$$$-й строке выведите единственное число — сумму минимумов на скользящих окнах длины $$$k_i$$$ на подотрезке $$$[a_{l_i}, \dots, a_{r_i}]$$$.

Система оценки
ПодзадачаБаллы Дополнительные ограничения Необх. подзадачи
16 $$$n, q \le 300$$$
212 $$$n, q \le 4000$$$1
38 $$$n, q \le 10\,000$$$1, 2
411 $$$n \le 4\,000$$$1, 2
510 $$$k_i$$$ равны во всех запросах
614 $$$a_i \le 2$$$
77 $$$a_i \le 20$$$6
815 $$$l_i = 1, r_i = n$$$
917 нет1–8
Пример
Входные данные
6 3
4 6 1 2 5 3
2 5 2
2 4 1
1 6 6
Выходные данные
4
9
1