题目描述

给定一个长为 $N$ 的序列 $S_i$，刚开始为时刻 $0$。

定义 $t$ 时刻第 $i$ 个数为 $S_i(t)$，那么：

$$\begin{cases} S_0(t)=0\\S_i(0)=S_i\\S_i(t)=\max\{S_{i-1}(t-1),S_i(t-1)\} \end{cases}$$

你将对 $Q$ 个操作进行评估，第 $j$ 个操作让时刻 $T_j$ 时的区间 $[L_j,R_j]$ 全部变为 $0$。

执行一个操作需要一定的代价，执行第 $j$ 个操作需要以下的代价：

$$\sum\limits_{k=L_j}^{R_j}S_k(T_j)$$

求每个操作需要的代价。

注意：每个操作都是独立的。

输入格式

第一行两个整数 $N,Q$ 代表序列长度和操作数。 第二行 $N$ 个整数 $S_i$ 代表这个序列。 接下来 $Q$ 行每行三个整数 $T_j,L_j,R_j$ 代表一个操作。

输出格式

$Q$ 行每行一个整数代表这个操作需要的代价。

样例

样例 #1 输入

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

样例 #1 输出

21
39
33
9
27

样例 #1 解释

• $S_i(0)=\{9,3,2,6,5\}$。
• $S_i(1)=\{9,9,3,6,6\}$，第一个操作需要的代价为 $9+9+3=21$。
• $S_i(2)=\{9,9,9,6,6\}$，第二个操作需要的代价为 $9+9+9+6+6=39$。
• $S_i(3)=\{9,9,9,9,6\}$，第三个操作需要的代价为 $9+9+9+9+6=33$。
• $S_i(4)=\{9,9,9,9,9\}$，第四个操作需要的代价为 $9$。
• $S_i(5)=\{9,9,9,9,9\}$，第五个操作需要的代价为 $27$。

样例 #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

样例 #2 输出

28
21
34
4
64
43
55
9
27
9

样例 #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

样例 #3 输出

9
9
3
4
3
4
5
9
9
9

样例 #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

样例 #4 输出

28
27
34
4
64
43
55
9
27
9

样例 #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

样例 #5 输出

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

数据范围与约定

本题采用捆绑测试。

• Subtask 1（10 pts）：$N,Q \le 200$。
• Subtask 2（10 pts）：$T_j$ 互相相等。
• Subtask 3（10 pts）：$L_j=R_j$。
• Subtask 4（10 pts）：$S_i \le 2$。
• Subtask 5（60 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $1 \le N \le 2 \times 10^5$。
• $1 \le Q \le 2 \times 10^5$。
• $1 \le S_i \le 10^9$。
• $1 \le T_j \le N$。
• $1 \le L_j \le R_j \le N$。