폭우 (Easy)

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

$Q$개의 쿼리가 주어진다. 각 쿼리는 $i$, $x$로 이루어지며, 이후로 $i$번째 칸의 벽 높이가 $x$가 된다는 뜻이다. 이때 $A_i < x$임이 보장된다.

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

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

두 번째 줄에 초기 높이 $A_1, A_2, \ldots, A_N$이 순서대로 주어진다. ($1 \le A_i \le 10^9$)

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

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

$Q$개의 줄에 걸쳐 각 쿼리를 수행한 뒤의 답을 한 줄에 하나씩 출력한다.