Description

You are given a sequence $S_i$ of length $N$, starting at time $0$.

Let the $i$-th value at time $t$ be $S_i(t)$. Then:

$$\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}$$

You will evaluate $Q$ operations. The $j$-th operation sets all values in the interval $[L_j, R_j]$ at time $T_j$ to $0$.

Performing an operation has a cost. The cost of the $j$-th operation is:

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

Compute the cost required for each operation.

Note: each operation is independent.

Input Format

The first line contains two integers $N, Q$, representing the length of the sequence and the number of operations.
The second line contains $N$ integers $S_i$, representing the sequence.
The next $Q$ lines each contain three integers $T_j, L_j, R_j$, representing one operation.

Output Format

Output $Q$ lines, each containing one integer, representing the cost required for the corresponding operation.

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

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

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

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

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

Hint

Sample 1 Explanation

• $S_i(0)=\{9,3,2,6,5\}$.
• $S_i(1)=\{9,9,3,6,6\}$. The cost of the first operation is $9+9+3=21$.
• $S_i(2)=\{9,9,9,6,6\}$. The cost of the second operation is $9+9+9+6+6=39$.
• $S_i(3)=\{9,9,9,9,6\}$. The cost of the third operation is $9+9+9+9+6=33$.
• $S_i(4)=\{9,9,9,9,9\}$. The cost of the fourth operation is $9$.
• $S_i(5)=\{9,9,9,9,9\}$. The cost of the fifth operation is $27$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (1 pts): $N, Q \le 200$.
• Subtask 2 (6 pts): All $T_j$ are equal.
• Subtask 3 (7 pts): $L_j=R_j$.
• Subtask 4 (6 pts): $S_i \le 2$.
• Subtask 5 (80 pts): No special restrictions.

For $100\%$ of the testdata:

• $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$.

Notes

Translated from The 19th Japanese Olympiad in Informatics, Final Round E Fire。

Translated by ChatGPT 5