레몬티처럼 달콤한 입술

다다스는 우현이에게 프러포즈할 준비를 하고 있다. 예전에는 그냥 "너를 좋아해" 라고 끝냈다면, 지금은 각별한 마음을 담아 보석을 많이 준비해 정말로 좋아하는 티를 낼 계획이다.

다다스는 수직선 위의 $0$ 이상 $N$ 이하의 정수 좌표에 기둥을 세우고 그 위에 보석을 올려놓는다. 좌표 $i$에 있는 기둥의 높이는 $A_i$이다. 만약 $A_i = 0$이라면 보석은 땅 위에 놓인 것이다. 따라서 보석은 총 $N+1$개 존재하며, 각 보석의 위치는 좌표 $i$에서 높이 $A_i$가 된다.

<그림 1>

다다스는 모든 보석이 조명에 비추어질 수 있도록 조명등을 설치하고자 한다. 각 조명등은 설치된 지점에서 아래 방향 좌우 $45$도 범위의 경계선과 그 안쪽을 비춘다. 기둥에 의해 그림자가 생기는 것은 고려하지 않는다.

조명등은 수직선 위 $0$ 이상 $N$ 이하의 정수 좌표에 양의 정수 높이로 설치된다. 해당 좌표에 설치된 기둥과 보석의 높이와 무관하게 설치해도 된다. 각 조명등의 설치 비용은 해당 조명등의 높이와 같다. 전체 조명등의 설치 비용은 각 조명등의 설치 비용의 합과 같다.

아래 그림은 일부 보석에게 빛이 닿지 않아 조명등이 부족한 상태를 보여주는 예시이다. 이와 같은 설치는 허용되지 않는다.

<그림 2>

반면 아래 그림은 모든 보석이 조명등 아래에 위치하는 올바른 설치 예시이다.

<그림 3>

변덕스러운 다다스는 총 $Q$회에 걸쳐 다음과 같이 명령을 내린다.

• x y : $A_x$의 값을 $y$로 수정한다.

초기 상태에서의 최소 설치 비용을 먼저 구하고, 이후 주어지는 $Q$회의 명령 각각에 대해 전체 조명등의 최소 설치 비용을 출력하라.

입력은 다음과 같은 형식으로 주어진다.

$N \ Q$

$A_0 \ A_1 \ \cdots \ A_N$

$x_1 \ y_1$

$x_2 \ y_2$

$\vdots$

$x_Q \ y_Q$

• $2 \le N \le 200\ 000$.
• $1 \le Q \le 200\ 000$.
• $0 \le A_i \le \min(N-i,i)$ ($0 \le i \le N$).
• $0 \leq x_i \leq N$ ($1 \leq i \leq Q$).
• $0 \leq y_i \leq \min(N - x_i, x_i)$ ($1\leq i \leq Q$).

첫째 줄에는 초기 상태에서의 최소 설치 비용을 출력한다.

둘째 줄부터 $Q$개의 줄에 걸쳐 각 명령을 처리한 직후의 최소 설치 비용을 한 줄에 하나씩 출력한다.

초기 상태에서는 아래와 같이 조명등을 배치하면, 총 설치 비용이 $4$로 최소가 된다.

첫 번째 쿼리를 처리한 직후에는 아래와 같이 조명등을 배치하면, 총 설치 비용이 $3$으로 최소가 된다.

1. $N \leq 5\ 000, Q \leq 5\ 000$. (30점)
2. 매 순간마다 $A_i=0$이다. (5점)
3. 매 순간마다 $A_i \geq 1$ ($1 \leq i \leq N-1$)이다. (5점)
4. 추가적인 제약 조건이 없다. (60점)