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