AT_past17_o 整地クエリ

You are given an integer sequence $ A = (A_1,A_2,\ldots,A_N) $ of length $ N $ . We define an operation against this sequence as follows. - Operation: choose an element of $ A $ , and add $ 1 $ or $ -1 $ . Given $ Q $ queries, process them in the given order. Each query is of one of the following two kinds. - `1 k d`: Add $ d $ to $ A_k $ (where $ d $ is $ 1 $ or $ -1 $ ). - `2 x`: Find the minimum number of operations to make all the elements of $ A $ equal $ x $ . The operations are not actually performed.

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Here, $ \mathrm{query}_i $ represents the $ i $ -th query, which is given in one of the following formats: > $ 1 $ $ k $ $ d $ > $ 2 $ $ x $

Print $ q $ lines, where $ q $ is the number of queries of the $ 2 $ -nd kind. The $ j $ -th $ (1\leq j \leq q) $ line should contain the answer to the $ j $ -th query of the second kind.

### Sample Explanation 1 Initially, $ A = (3,5,7,2) $ . - For the $ 1 $ -st query, it is optimal to add $ 1 $ to $ A_1 $ once, add $ -1 $ to $ A_2 $ once, add $ -1 $ to $ A_3 $ three times, and $ 1 $ to $ A_4 $ twice. Thus, $ 1+1+3+2=7 $ should be printed. - For the $ 2 $ -nd query, add $ 1 $ to $ A_1 $ . Now, $ A=(4,5,7,2) $ . - For the $ 3 $ -rd query, add $ -1 $ to $ A_2 $ . Now, $ A=(4,4,7,2) $ . - For the $ 4 $ -th query, it is optimal to add $ -1 $ to $ A_3 $ three times and $ 1 $ to $ A_4 $ twice. Thus, $ 3+2=5 $ should be printed. ### Constraints - All input values are integers. - $ 1\leq N,Q \leq 2\times 10^5 $ - $ |A_i| \leq 10^9 $ - For each query of the $ 1 $ -st kind, $ 1\leq k \leq N $ . - For each query of the $ 1 $ -st kind, $ d $ is $ 1 $ or $ -1 $ . - For each query of the $ 2 $ -nd kind, $ |x| \leq 10^9 $ . - There is at least one query of the $ 2 $ -nd kind.