위대한 도시 상트페테르부르크

상트페테르부르크는 비가 오지 않을 때 세계에서 가장 아름다운 도시다. 이 문제에서는 매일 비가 온다고 가정한다.

상트페테르부르크의 한 거리는 특이한 모양을 하고 있다. 길이가 1미터인 구간 $n$개가 좁은 띠를 이루고, 구간 $i$의 지면으로부터 높이는 $a_i$미터다. 띠의 깊이는 1미터이며, 앞과 뒤는 매우 높은 건물이 막고 있다. 그래서 비가 오면 빗물은 왼쪽 끝이나 오른쪽 끝으로 빠져나가지 못하고 고인다. 높이 $a_1, a_2, \ldots, a_n$이 주어질 때, 거리에 고이는 빗물의 양(立방미터)을 구하시오.

건설 회사가 $q$일 동안 이 거리에서 공사를 한다. $i$일째에는 $l_i$부터 $r_i$까지의 모든 구간에 아스팔트를 깔아서, 구간 $l_i, l_i+1, \ldots, r_i$의 높이를 각각 1미터씩 높인다. 공사 전과 매일 공사가 끝난 뒤에 고이는 빗물의 총량을 구하시오.

첫 줄에 구간의 개수 $n$과 공사 횟수 $q$가 주어진다 ($1 \le n, q \le 2 \cdot 10^5$). 둘째 줄에는 공사 전 각 구간의 높이를 나타내는 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^9$). 이어지는 $q$개의 줄에는 그날 공사하는 범위를 나타내는 두 정수 $l_i$와 $r_i$가 주어진다 ($1 \le l_i \le r_i \le n$).

$q+1$개의 정수를 출력한다. 첫 번째 값은 모든 공사 전 빗물의 양이고, 이후 값은 각 공사 후 빗물의 양이다.

그림은 첫 번째 예시에서 거리에 고이는 빗물의 양을 보여준다.