AT_abc421_f [ABC421F] Erase between X and Y

There is a sequence $ A $ . Initially, $ A=(0) $ . (That is, $ A $ is a sequence of length $ 1 $ containing $ 0 $ as its only element). You are given $ Q $ queries to process in order. The $ i $ -th query $ (1\leq i\leq Q) $ has one of the following forms: - `1 x`: Insert $ i $ immediately after the location where $ x $ appears in $ A $ . Specifically, let $ A_j $ be the $ j $ -th element of the current $ A $ and $ n $ be the length of $ A $ . For $ p $ such that $ A_p=x $ , update $ A $ to $ (A_1,\dots,A_p,i,A_{p+1},\dots,A_n) $ . It is guaranteed that $ A $ contains $ x $ immediately before processing this query. - `2 x y`: Remove all elements between $ x $ and $ y $ in $ A $ , and output the sum of the values of the removed elements. Specifically, let $ A_j $ be the $ j $ -th element of the current $ A $ and $ n $ be the length of $ A $ . For $ p $ and $ q $ such that $ A_p=x $ and $ A_q=y $ , output $ A_{\min(p,q)+1} + \dots + A_{\max(p,q)-1} $ and update $ A $ to $ (A_1,\dots,A_{\min(p,q)},A_{\max(p,q)},\dots,A_n) $ . It is guaranteed that $ A $ contains both $ x $ and $ y $ immediately before processing this query. Note that for any sequence of queries, the same value never appears multiple times in $ A $ during the process of handling queries, and thus the position where a value appears in $ A $ is unique (if it exists).

The input is given from Standard Input in the following format: > $ Q $ $ \text{query}_{1} $ $ \text{query}_{2} $ $ \vdots $ $ \text{query}_{Q} $ Here, $ \text{query}_{i} $ represents the $ i $ -th query and is given in one of the following forms: > 1 $ x $ > 2 $ x $ $ y $

Let $ q $ be the number of type $ 2 $ queries. Output $ q $ lines. The $ i $ -th line should contain the value to be output for the $ i $ -th type $ 2 $ query.

### Sample Explanation 1 Initially, $ A=(0) $ . - $ 1 $ st query: Insert $ 1 $ immediately after $ 0 $ . $ A $ becomes $ (0,1) $ . - $ 2 $ nd query: Insert $ 2 $ immediately after $ 1 $ . $ A $ becomes $ (0,1,2) $ . - $ 3 $ rd query: Insert $ 3 $ immediately after $ 0 $ . $ A $ becomes $ (0,3,1,2) $ . - $ 4 $ th query: Remove the elements between $ 2 $ and $ 3 $ , namely $ 1 $ , and output the sum of the removed values, which is $ 1 $ . $ A $ becomes $ (0,3,2) $ . - $ 5 $ th query: Insert $ 5 $ immediately after $ 2 $ . $ A $ becomes $ (0,3,2,5) $ . - $ 6 $ th query: Remove the elements between $ 0 $ and $ 5 $ , namely $ 3,2 $ , and output the sum of the removed values, which is $ 5 $ . $ A $ becomes $ (0,5) $ . ### Sample Explanation 2 In the $ 2 $ nd query, we remove all elements between $ 0 $ and $ 1 $ , but there are actually no such elements, so no elements are removed and the output value is $ 0 $ . ### Constraints - $ 1\leq Q \leq 5\times 10^5 $ - For the $ i $ -th query: - If it is a type $ 1 $ query: - $ 0\leq x < i $ - $ A $ contains $ x $ immediately before processing the query. - If it is a type $ 2 $ query: - $ 0\leq x < y < i $ - $ A $ contains both $ x $ and $ y $ immediately before processing the query. - All input values are integers.