人造序列题
题号：NC308100
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}我们定义一个长度为 2n+1 的序列 r_1,r_2,\dots,r_{2n+1} 为「人造序列」，当且仅当满足以下条件：
\hspace{23pt}\bullet\,对于所有 1 \leq i \leq n，都有 r_{2i-1} \geq r_{2i}

\hspace{15pt}现在给定一个长度为 2n+1 的序列 a_1,a_2,\dots,a_{2n+1}，你可以进行无限轮操作，每一轮操作：
\hspace{23pt}\bullet\,选择任意三个相邻的位置；
\hspace{23pt}\bullet\,将其中两个位置的数值同时加 1；
\hspace{23pt}\bullet\,将剩下一个位置的数值减 1。

\hspace{15pt}你的目标是通过最少轮操作，使序列 a 变成人造序列。
\hspace{15pt}此外，你需要支持 q 次单点修改：每次给出一对 (x,v)，表示将 a_x 修改为 v。
\hspace{15pt}每次修改后，你都需要重新计算最小操作次数。注意：这些修改是相互影响的。

输入描述:

\hspace{15pt}第一行输入两个整数 n, q \left(1 \leq n \leq 10^5;\, 1 \leq q \leq 2 \times 10^5\right)，表示序列长度、修改次数。 
\hspace{15pt}第二行输入 2n+1 个整数 a_1,a_2,\dots,a_{2n+1} \left(-10^9 \leq a_i \leq 10^9\right)，表示初始序列。 
\hspace{15pt}此后 q 行，第 i 行输入两个整数 x_i, v_i \left(1 \leq x_i \leq 2n+1;\ -10^9 \leq v_i \leq 10^9\right)，表示第 i 次修改操作的参数。

输出描述:

\hspace{15pt}第一行输出一个整数，表示初始序列变成人造序列所需的最小操作次数。 
\hspace{15pt}此后 q 行，每行输出一个整数，表示修改后的最小操作次数。
示例1

输入

复制 
3 7
3 3 2 5 1 3 1
1 2
1 3
3 2
3 5
2 4
2 3
4 4

输出

复制 
2
3
2
2
1
2
1
1

说明

对于序列 [3,3,2,5,1,3,1]，执行两次位置 3 加 1，位置 4 减 1，位置 5 加 1。最终序列 [3,3,4,3,3,3,1]，满足要求。

修改一次后，对于序列 [2,3,2,5,1,3,1]，执行操作：位置 2 减 1，位置 3 加 1，位置 4 加 1；位置 3 加 1，位置 4 减 1，位置 5 加 1；位置 3 加 1，位置 4 减 1，位置 5 加 1；最终序列 [2,2,5,4,3,3,1]，满足要求。
示例2

输入

复制 
3 7
-882073681 -708416144 -412725361 249140755 -714769963 106737160 412181794
2 585842503
1 -697370064
6 -929022307
6 387510778
7 636011478
5 -438802112
6 -262455284

输出

复制 
641341668
1144711654
1057424804
651736200
1197811613
1197811613
1059827687
734844656

备注: