34251번 - 레몬티처럼 달콤한 입술 서브태스크

문제

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

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

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

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

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

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

변덕스러운 다다스는 총 $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$

출력

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

둘째 줄부터 $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$).

서브태스크

힌트