폭우

일렬로 놓인 $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$개의 줄에 걸쳐 각 쿼리를 수행했을 때의 답을 출력한다.