문제
취미로 요리를 하는 홍윤이는, N개의 정수로 구성된 수열을 적당히 잘라,
최대한 맛있게 요리하려고 한다.
한 구간의 맛있음은, 그 구간의 최댓값과 최솟값의 차로 정의되고,
전체 수열의 맛있음은 잘려진 각 구간의 맛있음의 합으로 정의된다.
예를 들어 수열 [1 4 1 5 3 6]을 [1 4 1]과 [5 3 6]으로 쪼갰다면
맛있음의 정도는 (4-1) + (6-3) = 6이다.
또한, 구간 [l, r]의 모든 값들에 x를 추가하는 형태의 업데이트가 Q개 주어진다.
각 업데이트 이후, 전체 수열의 맛있음 정도의 최댓값을 출력하여라.
[제약 조건]
1 ≤ N, Q ≤ 200 000
−108 ≤ ai ≤ 108
1 ≤ l ≤ r ≤ n
−108 ≤ x ≤ 108
[Subtask]
Subtask #1 (15점) : 1 ≤ N, Q ≤ 200
Subtask #2 (30점) : 1 ≤ N, Q ≤ 3000
Subtask #3 (55점) : 추가 제한 조건 없음
입력
다음과 같은 형태로 입력이 주어진다.
[입력 형식]
N Q
a1 a2 ... an
l1 r1 x1
l2 r2 x2
...
lQ rQ xQ
출력
Q개의 줄에 걸쳐 각 업데이트 이후 답을 출력한다.
예제1
입력
43
1234
121
112
231
출력
2
2
0
예제2
입력
43
2021
441
223
132
출력
2
1
3
출처
coci 2020/2021 contest5