AT_ndpc2026_g 口

長さ $ N $ の整数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。 $ Q $ 個のクエリを処理してください。クエリでは $ 1 \leq i \leq N $ を満たす整数 $ i $ および非負整数 $ v $ が与えられるので、 $ A_i $ を $ v $ に更新して、以下の問題を解いてください。(更新は永続的です。) > $ 1 $ から $ N $ の番号がついた $ N $ 人の人が口を開けた状態で数直線上に並んでいます。人 $ i $ は地点 $ i $ にいます。各人は **空腹度** というパラメータを持っていて、人 $ i $ の空腹度は $ A_i $ です。 > あなたはキャンディを無数に持っています。あなたはみんなにキャンディを食べさせてあげるために次の一連の行動を $ 1 $ 回だけ行うことにしました。 > > - まず、 $ 1 \leq x \leq N $ を満たす整数 $ x $ を選び、地点 $ x $ に立つ。 > - そして、次の操作を $ 0 $ 回以上自由な回数行う。 > - 今いる地点を $ y $ として、 $ y-1, y, y+1 $ のいずれかの地点に移動する。ただし、人が立っていない地点に移動することは出来ない。 > - 今いる地点にいる人の口にキャンディを $ 1 $ 個放り込む。 > > 行動を終了した時点で、人 $ i $ の口に放り込んだキャンディの個数を $ B_i $ とします。 $ \displaystyle \sum_{i=1}^N \vert A_i - B_i \vert $ としてあり得る最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ i $ $ v $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリへの答えを出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ Q \leq 10 $ であるデータセットに正解した場合、 $ 2 $ 点が与えられる。 ### Sample Explanation 1 $ 1 $ 番目のクエリを処理することを考えます。 $ A=(1,0,0,2) $ に対して問題を解けばよいです。 この時、以下の行動を取ることで目的関数の値を $ 1 $ にすることができて、これが最適です。 - $ x=3 $ を選び、地点 $ 3 $ に立つ。 - 地点 $ 4 $ に移動して人 $ 4 $ の口にキャンディを $ 1 $ 個放り込む。 - 再び地点 $ 4 $ に移動して人 $ 4 $ の口にキャンディを $ 1 $ 個放り込む。 - 操作を終了する。操作後の $ B $ は $ (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 $ - 入力される値は全て整数