AT_ndpc2026_g 口

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 $ .

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 $

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

### Partial Score This problem has partial scoring. - If you solve the dataset with $ Q \leq 10 $ , you will get $ 2 $ points. ### Sample Explanation 1 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