题目描述

译自 JOI 2020 Final T5「火事 / Fire」

在 JOI 世界里有 $N$ 个地区排成一条线。为了方便，我们将这些地区编号为 $1$ 到 $N$。突然，各个地区都起火了。在时刻 $0$，第 $i$ 个区的火势大小为 $S_i$。

此时（时刻 $0$），一阵风从 $1$ 号地区一直吹到了 $N$ 号地区，并且这阵风会一直持续。对于每两个相邻的地区，如果 $t$ 时刻上风地区的火势比下风地区的强，$t+1$ 时刻下风地区的火势大小将变为 $t$ 时刻上风地区的火势，否则 $t+1$ 和 $t$ 时刻时下风地区的火势大小不变。

形式化地说，如果 $t$ 时刻 $i$ 地区的火势为 $S_i(t)$，则 $S_i(t)=\max\{S_{i-1}(t-1),S_i(t-1)\}$，其中 $S_0(t)=0$，$S_i(0)=S_i$。

你是一位消防员。现在，你想到了 $Q$ 种灭火方案。你的第 $j$ 种方案是在 $T_j$ 时刻对 $[L_j, R_j]$ 中的所有地区使用灭火剂完全扑灭火灾。

对于一个火势大小为 $s$ 的城市，你将需要 $s$ 升的灭火剂来扑灭火灾。因此，执行方案 $j$ 总共要花费 $S_{L_j}(T_j)+S_{L_j+1}(T_j)+\cdots +S_{R_j}(T_j)$ 升灭火剂。

为了更好地选取灭火方案，你的任务是编写一个程序，给出 $0$ 时刻的火势大小，计算各个方案所需的灭火剂量。

输入格式

第一行两个数 $N, Q$，含义如题面所示。

接下来一行 $N$ 个数 $S_1 \dots S_N$，表示初始时的火势大小。

接下来 $Q$ 行每行三个数 $T_j, L_j, R_j$，表示方案 $j$ 的相关信息。

输出格式

输出 $Q$ 行，第 $i$ 行表示方案 $j$ 所需的灭火剂量。

样例 1

输入

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

输出

21
39
33
9
27

时刻 $0$ 时地区 $1$ 到地区 $N$ 的火势大小分别为 $9, 3, 2, 6, 5$。

时刻 $1$ 时地区 $1$ 到地区 $N$ 的火势大小分别为 $9, 9, 3, 6, 6$。方案 $1$ 需要的灭火剂量为 $9+9+3=21$ 升。

时刻 $2$ 时地区 $1$ 到地区 $N$ 的火势大小分别为 $9, 9, 9, 6, 6$。方案 $2$ 需要的灭火剂量为 $9+9+9+6+6=39$ 升。

时刻 $3$ 时地区 $1$ 到地区 $N$ 的火势大小分别为 $9, 9, 9, 9, 6$。方案 $3$ 需要的灭火剂量为 $9+9+9+6=33$ 升。

时刻 $4$ 时地区 $1$ 到地区 $N$ 的火势大小分别为 $9, 9, 9, 9, 9$。方案 $4$ 需要的灭火剂量为 $9$ 升。

时刻 $5$ 时地区 $1$ 到地区 $N$ 的火势大小分别为 $9, 9, 9, 9, 9$。方案 $5$ 需要的灭火剂量为 $9+9+9=27$ 升。

该样例满足子任务 $1$ 和子任务 $5$ 的限制。

样例 2

输入

10 10
3 1 4 1 5 9 2 6 5 3
1 1 6
2 8 10
4 2 7
8 3 3
6 1 10
3 2 8
5 1 9
7 4 5
9 7 9
10 10 10

输出

28
21
34
4
64
43
55
9
27
9

该样例满足子任务 $1$ 和子任务 $5$ 的限制。

样例 3

输入

10 10
3 1 4 1 5 9 2 6 5 3
1 6 6
2 8 8
4 2 2
8 3 3
6 1 1
3 4 4
5 5 5
7 10 10
9 8 8
10 7 7

输出

9
9
3
4
3
4
5
9
9
9

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

样例 4

输入

10 10
3 1 4 1 5 9 2 6 5 3
7 1 6
7 8 10
7 2 7
7 3 3
7 1 10
7 2 8
7 1 9
7 4 5
7 7 9
7 10 10

输出

28
27
34
4
64
43
55
9
27
9

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

样例 5

输入

20 20
2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1
1 1 14
2 3 18
4 10 15
8 2 17
9 20 20
4 8 19
7 2 20
11 1 5
13 2 8
20 1 20
2 12 15
7 1 14
12 7 18
14 2 17
9 19 20
12 12 12
6 2 15
11 2 15
19 12 17
4 1 20

输出

25
30
12
32
2
24
38
10
14
40
8
28
24
32
4
2
28
28
12
40

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

数据范围与提示

对于所有测试数据 $1 \le N,Q \le 2 \times 10^5$，$1 \le S_i \le 10^9$，$1 \le L_j, R_j, T_j \le N$。

子任务编号	分值	具体限制
1	$1$	$1 \le N,Q \le 200$
2	$6$	$T_1 = T_2 = \ldots = T_Q$
3	$7$	$L_j = R_j$ $(1 \le j \le Q)$
4	$6$	$S_i \le 2$ $(1 \le i \le N)$
5	$80$