폭우 (Hard)

일렬로 놓인 $N$개의 칸에 끊임없는 비가 내린다. $i$번째 칸에는 초기에 높이 $A\_i$의 벽이 세워져 있다. 벽 안에 고인 비가 가득 차면 왼쪽 끝과 오른쪽 끝의 공허로 넘쳐서 사라진다. 또한, 빗물은 일렬로 놓인 좌우 방향 이외의 방향으로 이동하지 않는다.

$Q$개의 쿼리가 주어진다. 각 쿼리는 $l, r, x$로 이뤄지며, $\[l, r]$ 구간의 칸에 세워진 벽의 높이가 이후로 $x$가 된다는 의미이다.

각 쿼리가 끝날 때마다 최대 얼마만큼의 비가 고이게 될 수 있는지 답하라.

첫 번째 줄에 $N$, $Q$가 차례대로 주어진다. ($1 \le N \le 100\\,000; 1 \le Q \le 100\\,000$)

두 번째 줄에 초기 높이 $A\_i$가 순서대로 주어진다. ($1 \le A\_i \le 10^9$)

세 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄마다 쿼리를 의미하는 세 정수 $l, r, x$가 공백으로 구분되어 주어진다. ($1 \le l \le r \le N; 1 \le x \le 10^9$)

입력으로 주어지는 모든 수는 정수이다.

$Q$개의 줄에 걸쳐 각 쿼리를 수행했을 때의 답을 출력한다.