AT_arc168_f [ARC168F] Up-Down Queries

[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\

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

答えを出力せよ．

### 制約 - $ 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) $ の値となる．