AT_past17_o 整地クエリ

長さ $ N $ の整数列 $ A = (A_1,A_2,\ldots,A_N) $ が与えられます。 この数列に対する操作を以下のように定めます。 - 操作： $ A $ の要素を $ 1 $ つ選んで、 $ 1 $ または $ -1 $ を加算する。 クエリが $ Q $ 個与えられるので、与えられた順番に処理してください。クエリは次の $ 2 $ 種類のいずれかです。 - `1 k d` : $ A_k $ に $ d $ を加算する ( $ d $ は $ 1 $ または $ -1 $ )。 - `2 x` : $ A $ の要素を全て $ x $ にするために必要な操作回数の最小値を求める。ただし、実際には操作は行わない。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ ただし、 $ \mathrm{query}_i $ は $ i $ 個目のクエリを表しており、次の形式のいずれかで与えられる。 > $ 1 $ $ k $ $ d $ > $ 2 $ $ x $

$ 2 $ 番目の形式のクエリの回数を $ q $ 回として、 $ q $ 行出力せよ。 $ j\ (1\leq j \leq q) $ 行目には、 $ 2 $ 番目の形式のクエリのうち $ j $ 個目のものに対する答えを出力せよ。

### Sample Explanation 1 最初、 $ A = (3,5,7,2) $ です。 - $ 1 $ 番目のクエリでは、 $ A_1 $ に $ 1 $ を足す操作を $ 1 $ 回、 $ A_2 $ に $ -1 $ を足す操作を $ 1 $ 回、 $ A_3 $ に $ -1 $ を足す操作を $ 3 $ 回、 $ A_4 $ に $ 1 $ を足す操作を $ 2 $ 回行うのが最適です。よって、 $ 1+1+3+2=7 $ を出力します。 - $ 2 $ 番目のクエリでは、 $ A_1 $ に $ 1 $ が足されます。 $ A=(4,5,7,2) $ になります。 - $ 3 $ 番目のクエリでは、 $ A_2 $ に $ -1 $ が足されます。 $ A=(4,4,7,2) $ になります。 - $ 4 $ 番目のクエリでは、 $ A_3 $ に $ -1 $ を足す操作を $ 3 $ 回、 $ A_4 $ に $ 1 $ を足す操作を $ 2 $ 回行うのが最適です。よって、 $ 3+2=5 $ を出力します。 ### Constraints - 入力は全て整数 - $ 1\leq N,Q \leq 2\times 10^5 $ - $ |A_i| \leq 10^9 $ - $ 1 $ 番目の形式のクエリについて、 $ 1\leq k \leq N $ - $ 1 $ 番目の形式のクエリについて、 $ d $ は $ 1 $ または $ -1 $ - $ 2 $ 番目の形式のクエリについて、 $ |x| \leq 10^9 $ - $ 2 $ 番目の形式のクエリが少なくとも $ 1 $ つ与えられる