COCI '20 Contest 5 #5 Sjeckanje

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Paula likes to prepare stir fry. In order to make it as yummy as possible, she needs to chop a sequence of integers into segments of the maximum total value.

The value of a segment is the difference of its maximum and minimum. The value of a chopped sequence is the sum of the values of the segments.

For example if we chop the sequence into segments and , the total value is .

There will be updates of the form "add to the elements on indices ". After each update, answer the query "What is the maximum possible value of the chopped sequence?".

Input Specification

The first line contains integers and , the length of the sequence and the number of updates.

The second line contains integers , the sequence Paula needs to chop.

Each of the following lines contains integers , , and , describing an update.

Output Specification

Output lines, the maximum possible value of the sequence after each update.

115
240

Sample Input 1

4 3
1 2 3 4
1 2 1
1 1 2
2 3 1

Sample Output 1

2
2
0

Explanation for Sample Output 1

Possible optimal choppings after each update are respectively: , , and .

Sample Input 2

4 3
2 0 2 1
4 4 1
2 2 3
1 3 2

Sample Output 2

2
1
3