[ARC168F] Up-Down Queries

有长为 $N$ 的操作序列 $x=(x_1,x_2,\cdots,x_N) $，对 $f(x)$ 定义如下。 有长为 $M$ 初始全 $0$ 的序列 $y$ ，对于 $ i=1,2,\cdots,N $ 依次进行如下操作。 - 对 $ j $ ($ 1\ \leq\ j\ \leq\ x_i $)，令 $ y_j = \max(y_j-1,0) $。 - 对 $ j $ ($ x_i\ <\ j\ \leq\ M $)，令 $ y_j= y_j+1 $。 所有操作结束时 $y$ 的和即为 $f(x)$ 。 现在给出初始的操作序列 $x$，有 $Q$ 次修改操作，将 $x_i$ 修改为 $k$，每次操作后输出当前的 $f(x)$。

[problemUrl]: https://atcoder.jp/contests/arc168/tasks/arc168_f 各要素が $ 0 $ 以上 $ M $ 以下で長さが $ N $ の整数列 $ x=(x_1,x_2,\cdots,x_N) $ に対し，$ f(x) $ を次のように定義します． - 長さ $ M $ の整数列 $ y=(y_1,y_2,\cdots,y_M) $ を用意する． 最初，$ y $ の要素はすべて $ 0 $ にする． その後，各 $ i=1,2,\cdots,N $ に対しこの順に以下の操作を行う． - 各整数 $ j $ ($ 1\ \leq\ j\ \leq\ x_i $) に対し，$ y_j $ の値を $ \max(y_j-1,0) $ で置き換える． - 各整数 $ j $ ($ x_i\ <\ j\ \leq\ M $) に対し，$ y_j $ の値を $ y_j+1 $ で置き換える． - すべての操作が終わった時点での $ y $ の要素の総和を $ f(x) $ の値とする． 各要素が $ 0 $ 以上 $ M $ 以下で長さが $ N $ の整数列 $ A=(A_1,A_2,\cdots,A_N) $ が与えられます． $ Q $ 個のクエリを処理してください． - $ i $ 番目のクエリ: 整数 $ X_i,Y_i $ が与えられるので，$ A_{X_i} $ の値を $ Y_i $ で置き換える． その後，$ f(A) $ の値を出力する．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ Q $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_Q $ $ Y_Q $

答えを出力せよ．

3 4 2
1 2 3
1 4
3 0

2
6

7 2 9
2 0 2 2 0 1 0
1 1
3 0
4 0
4 1
6 1
3 2
2 0
3 2
2 0

4
7
11
9
9
6
6
6
6

20 200000 10
39664 143179 193565 153887 16141 91985 51452 155409 116777 190060 87620 64458 106481 51272 9108 100995 139248 18243 181424 6182
4 196305
13 59753
8 96194
6 57037
19 125781
16 142779
15 13967
10 17772
16 84763
12 17283

1145670
1234421
1352851
1352851
1464137
1380569
1380569
1608611
1724643
1736769

### 制約 - $ 1\ \leq\ N,M,Q\ \leq\ 250000 $ - $ 0\ \leq\ A_i\ \leq\ M $ - $ 1\ \leq\ X_i\ \leq\ N $ - $ 0\ \leq\ Y_i\ \leq\ M $ - 入力される値はすべて整数． ### Sample Explanation 1 まず $ 1 $ 番目のクエリを考えます． $ A_1 $ の値を $ 4 $ で置き換え，$ A=(4,2,3) $ になります． そして，$ f(A) $ の値は次のように求まります． - $ y=(0,0,0,0) $ を用意する． - $ A_1=4 $ について操作を行い，$ y=(0,0,0,0) $ になる． - $ A_2=2 $ について操作を行い，$ y=(0,0,1,1) $ になる． - $ A_3=3 $ について操作を行い，$ y=(0,0,0,2) $ になる． - $ y $ の要素の総和 $ =2 $ が $ f(A) $ の値となる． 次に $ 2 $ 番目のクエリを考えます． $ A_3 $ の値を $ 0 $ で置き換え，$ A=(4,2,0) $ になります． そして，$ f(A) $ の値は次のように求まります． - $ y=(0,0,0,0) $ を用意する． - $ A_1=4 $ について操作を行い，$ y=(0,0,0,0) $ になる． - $ A_2=2 $ について操作を行い，$ y=(0,0,1,1) $ になる． - $ A_3=0 $ について操作を行い，$ y=(1,1,2,2) $ になる． - $ y $ の要素の総和 $ =6 $ が $ f(A) $ の値となる．