AT_ndpc2026_g.Mouth

You are given an integer sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$.
Process $Q$ queries. In each query, you are given an integer $i$ ($1 \leq i \leq N$) and a non-negative integer $v$. Update $A_i$ to $v$, and then solve the following problem. (The updates are permanent.)

There are $N$ people standing on a number line at positions $1$ to $N$, each with their mouth open. Person $i$ is at position $i$. Each person has a parameter called hunger, and the hunger of person $i$ is $A_i$.
You have an unlimited number of candies. You decide to perform the following sequence of actions exactly once to feed them:

• First, choose an integer $x$ such that $1 \leq x \leq N$, and stand at position $x$.
• Then, perform the following operations any number of times (possibly zero):
  • Let your current position be $y$. Move to position $y-1$, $y$, or $y+1$. However, you cannot move to a position where no person is standing.
  • Throw one candy into the mouth of the person at your current position.

After finishing all operations, let $B_i$ be the number of candies given to person $i$. Find the minimum possible value of $\displaystyle \sum_{i=1}^N \vert A_i - B_i \vert$.

给你一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$。
你需要处理 $Q$ 个查询。在每个查询中，你将收到一个整数 $i$（满足 $1 \leq i \leq N$）和一个非负整数 $v$。请将 $A_i$ 更新为 $v$，然后求解如下问题。（这些更新是永久性的。）

数轴上有 $N$ 个人，分别站在位置 $1$ 到 $N$ 上，且每个人张着嘴。第 $i$ 个人位于位置 $i$。每个人有一个称为饥饿值的参数，其中第 $i$ 个人的饥饿值为 $A_i$。
你拥有无限数量的糖果。你决定恰好执行以下一系列操作一次，以喂饱他们：

• 首先，选择一个整数 $x$（满足 $1 \leq x \leq N$），并站在位置 $x$。
• 然后，重复执行以下操作任意次数（可以为零次）：
  • 设你当前所在位置为 $y$。你可以移动到位置 $y-1$、$y$ 或 $y+1$。但你不能移动到没有人的位置。
  • 向你当前位置上的人投掷一颗糖果。

在完成所有操作后，设 $B_i$ 表示分发给第 $i$ 个人的糖果数量。求 $\displaystyle \sum_{i=1}^N \vert A_i - B_i \vert$ 的最小可能值。

The input is given from standard input in the following format:

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

Each query is given in the following format:

$i$ $v$

输入从标准输入中按以下格式给出：

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询按以下格式给出：

$i$ $v$

Print $Q$ lines. For the $i$-th line, output the answer to the $i$-th query.

输出 $Q$ 行。对于第 $i$ 行，输出第 $i$ 个查询的答案。

Partial Score

This problem has partial scoring.

• If you solve the dataset with $Q \leq 10$, you will get $2$ points.

Sample 1 Explanation:
Consider processing the first query. You need to solve the problem for $A = (1,0,0,2)$.
In this case, the following actions achieve a value of $1$, which is optimal:

• Choose $x=3$ and stand at position $3$.
• Move to position $4$ and give one candy to person $4$.
• Stay at position $4$ again and give another candy to person $4$.
• End the operations. The resulting $B$ becomes $(0,0,0,2)$.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $0 \leq A_i \leq 10^9$
• $1 \leq i \leq N$
• $0 \leq v \leq 10^9$
• All input values are integers

部分得分

本题采用部分得分制。

• 若你解决了满足 $Q \leq 10$ 的数据集，则可获得 $2$ 分。

样例 1 解释：
考虑处理第一个查询。此时需针对 $A = (1,0,0,2)$ 求解。
在此情况下，以下操作可达到最优值 $1$：

• 选择 $x=3$，并站在位置 $3$；
• 移动到位置 $4$，并向第 $4$ 个人给予一颗糖果；
• 再次停留在位置 $4$，并向第 $4$ 个人再给予一颗糖果；
• 结束操作。最终得到的 $B$ 为 $(0,0,0,2)$。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $0 \leq A_i \leq 10^9$
• $1 \leq i \leq N$
• $0 \leq v \leq 10^9$
• 所有输入值均为整数