[AdditionalFile5570.zip](file://AdditionalFile5570.zip?type=additional_file)

#5570. 「ROIR 2026 Day2」滑动窗口

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 ROI Regional 2026 Day2 T3. Скользящие окна

给定一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$。

长度为 $k$ 的滑动窗口是指数组上所有连续长度为 $k$ 的子段，即 $[a_i, \dots, a_{i+k-1}]$（$i$ 从 $1$ 到数组长度 $-k+1$）。

需要回答 $q$ 个询问：对于给定的 $l, r, k$，在子数组 $[a_l, \dots, a_r]$ 上，计算所有长度为 $k$ 的滑动窗口的最小值之和。

输入格式

第一行两个整数 $n, q$ $(1 \leq n, q \leq 100000)$，表示数组长度和查询数量。

第二行 $n$ 个整数 $a_1, \dots, a_n$ $(1 \leq a_i \leq 10^9)$，表示数组元素。

接下来 $q$ 行，每行三个整数 $l_i, r_i, k_i$ $(1 \leq l_i \leq r_i \leq n,\ 1 \leq k_i \leq r_i - l_i + 1)$，表示第 $i$ 个查询的左右端点和窗口长度。

输出格式

输出 $q$ 行，每行一个整数，表示对应查询的滑动窗口最小值之和。

样例

输入

6 3
4 6 1 2 5 3
2 5 2
2 4 1
1 6 6

输出

4
9
1

数据范围与提示

详细子任务附加限制及分值如下表所示：