AT_past202309_l 平均クエリ

You are given a sequence of length $ N $ consisting of positive integers, $ A=(A_1,A_2,\ldots,A_N) $ , and an empty set $ S $ . Let us define $ f(L,R) $ as $ \displaystyle\sum_{i=L+1}^R \frac{A_i}{R-L} $ for a pair of integers $ (L,R) $ such that $ 0\leq L

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ query_1 $ $ query_2 $ $ \vdots $ $ query_Q $ Each $ query_i $ starts with a number $ t_i $ $ (1\leq t_i\leq 2) $ representing the type of the given query. It is followed by an integer $ x $ $ (0\leq x\leq N) $ if $ t_i=1 $ , and nothing if $ t_i=2 $ . That is, $ query_i $ is in one of the following formats: > $ 1 $ $ x $ > $ 2 $

Print $ k $ lines, where $ k $ is the number of queries of type $ 2 $ among the given $ Q $ queries. The $ i $ -th line $ (1\leq i\leq k) $ should contain the answer to the $ i $ -th query of type $ 2 $ .

### Sample Explanation 1 The values of $ f(L,R) $ are as follows. - $ f(0,1)=\frac{2}{1}=\frac{2}{1} $ - $ f(0,2)=\frac{2+3}{2}=\frac{5}{2} $ - $ f(0,3)=\frac{2+3+5}{3}=\frac{10}{3} $ - $ f(1,2)=\frac{3}{1}=\frac{3}{1} $ - $ f(1,3)=\frac{3+5}{2}=\frac{8}{2} $ - $ f(2,3)=\frac{5}{1}=\frac{5}{1} $ The queries are processed as follows. - The first query is of type $ 1 $ and gives $ x=0 $ . Since $ 0\notin S $ , add $ 0 $ to $ S $ . - The second query adds $ 3 $ to $ S $ . - The third query is of type $ 2 $ , and we have $ S= \{ 0,3 \} $ at this point, so $ (0,3) $ is the only $ (l,r) $ such that $ l,r\in S $ and $ 0\leq l