Problem Background

Due to the large size of the data package, this problem only tests Subtasks 4 & 5.

For Subtasks 1 & 2 & 3, please test here.

Problem Description

Given a sequence \( S_i \) of length \( N \), initially at time \( 0 \).

Define \( S_i(t) \) as the value of the \( i \)-th number at time \( t \), then:

\[ \left\{ \begin{array}{ll} S_0(t)=0 \\ S_i(0)=S_i \\ S_i(t)=\max\{S_{i-1}(t-1),S_i(t-1)\} \end{array} \right. \]

You will evaluate \( Q \) operations, where the \( j \)-th operation sets the interval \([L_j, R_j]\) to \( 0 \) at time \( T_j \).

Executing an operation incurs a cost, and the cost for the \( j \)-th operation is:

\[ \sum_{k=L_j}^{R_j} S_k(T_j) \]

Find the cost required for each operation.

Note: Each operation is independent.

Input Format

The first line contains two integers \( N \) and \( Q \), representing the length of the sequence and the number of operations, respectively.
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 an operation.

Output Format

Output \( Q \) lines, each containing a single integer representing the cost required for that operation.

Sample Input and Output

Input Sample #1

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

Output Sample #1

21
39
33
9
27

Input Sample #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

Output Sample #2

28
21
34
4
64
43
55
9
27
9

Input Sample #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

Output Sample #3

9
9
3
4
3
4
5
9
9
9

Input Sample #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

Output Sample #4

28
27
34
4
64
43
55
9
27
9

Input Sample #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

Output Sample #5

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

Notes

Sample 1 Explanation

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

Data Size and Constraints

This problem uses batched testing.

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

For \( 100\% \) of the data:

• \( 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.

见题面 Input 部分

见题面 Output 部分