취미로 요리를 하는 홍윤이는, 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

−10⁸ ≤ a_i ≤ 10⁸

1 ≤ l ≤ r ≤ n

−10⁸ ≤ x ≤ 10⁸

[Subtask]

Subtask #1 (15점) : 1 ≤ N, Q ≤ 200

Subtask #2 (30점) : 1 ≤ N, Q ≤ 3000

Subtask #3 (55점) : 추가 제한 조건 없음

맛있는 요리 timer 2s memory 512MB

맛있는 요리 2s 512MB