JOI 村有 $N$ 个区块，编号为 $1$ 到 $N$。这些区块按编号顺序排成一行。现在，每个区块都发生了火灾，时刻 $0$ 时第 $i$ 个区块（$1 \leq i \leq N$）的火势为 $S_i$（$S_i > 0$）。

在时刻 $0$，从区块 $1$ 向区块 $N$ 的方向开始刮风。对于相邻的两个区块，在时刻 $t$（$0 \leq t$）时，如果上风区块的火势比下风区块的火势强，则在时刻 $t+1$ 时，下风区块的火势会变为时刻 $t$ 上风区块的火势。否则，在时刻 $t+1$ 时，下风区块的火势保持不变。也就是说，设时刻 $t$（$0 \leq t$）第 $i$ 个区块的火势为 $S_i(t)$，则对于 $1 \leq t$，有 $S_i(t) = \max\{S_{i-1}(t-1), S_i(t-1)\}$。其中，任意 $t$（$0 \leq t$）下 $S_0(t) = 0$，任意 $i$（$1 \leq i \leq N$）下 $S_i(0) = S_i$。

你作为消防员，计划了 $Q$ 次灭火行动。你只会选择其中一个计划来执行。第 $j$ 个计划（$1 \leq j \leq Q$）是在时刻 $T_j$，对所有满足 $L_j \leq k \leq R_j$ 的区块 $k$ 喷洒灭火剂，将这些区块的火扑灭。扑灭火势为 $s$ 的区块需要 $s$ 升灭火剂。也就是说，第 $j$ 个计划需要 $S_{L_j}(T_j) + S_{L_j+1}(T_j) + \cdots + S_{R_j}(T_j)$ 升灭火剂。

为了选择要执行的计划，你需要知道每个计划所需的灭火剂量。

给定时刻 $0$ 的火势信息和灭火计划的信息，请编写程序，计算每个计划所需的灭火剂总量。

输入从标准输入读入，格式如下。所有输入均为整数。

$N$ $Q$
$S_1$ $S_2$ $\cdots$ $S_N$
$T_1$ $L_1$ $R_1$
$\vdots$
$T_Q$ $L_Q$ $R_Q$

输出 $Q$ 行。第 $j$ 行（$1 \leq j \leq Q$）输出第 $j$ 个计划所需的灭火剂总量。

数据范围

• $1 \leq N \leq 200\,000$。
• $1 \leq Q \leq 200\,000$。
• $1 \leq S_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。
• $1 \leq T_j \leq N$（$1 \leq j \leq Q$）。
• $1 \leq L_j \leq R_j \leq N$（$1 \leq j \leq Q$）。

子任务

1.（1 分）$N \leq 200$，$Q \leq 200$。
2.（6 分）$T_1 = T_2 = \cdots = T_Q$。
3.（7 分）$L_j = R_j$（$1 \leq j \leq Q$）。
4.（6 分）$S_i \leq 2$（$1 \leq i \leq N$）。
5.（80 分）无额外限制。

样例说明 1

• 时刻 $0$ 各区块的火势为 $9, 3, 2, 6, 5$。
• 时刻 $1$ 各区块的火势为 $9, 9, 3, 6, 6$，因此第 $1$ 个计划所需灭火剂为 $9 + 9 + 3 = 21$ 升。
• 时刻 $2$ 各区块的火势为 $9, 9, 9, 6, 6$，因此第 $2$ 个计划所需灭火剂为 $9 + 9 + 9 + 6 + 6 = 39$ 升。
• 时刻 $3$ 各区块的火势为 $9, 9, 9, 9, 6$，因此第 $3$ 个计划所需灭火剂为 $9 + 9 + 9 + 6 = 33$ 升。
• 时刻 $4$ 各区块的火势为 $9, 9, 9, 9, 9$，因此第 $4$ 个计划所需灭火剂为 $9$ 升。
• 时刻 $5$ 各区块的火势为 $9, 9, 9, 9, 9$，因此第 $5$ 个计划所需灭火剂为 $9 + 9 + 9 = 27$ 升。

输入样例 $1$ 满足子任务 $1, 5$ 的限制。

样例说明 2

输入样例 $2$ 满足子任务 $1, 5$ 的限制。

样例说明 3

输入样例 $3$ 满足子任务 $1, 3, 5$ 的限制。

样例说明 4

输入样例 $4$ 满足子任务 $1, 2, 5$ 的限制。

样例说明 5

输入样例 $5$ 满足子任务 $1, 4, 5$ 的限制。

由 ChatGPT 4.1 翻译