AT_abc432_e [ABC432E] Clamp

You are given an integer sequence $ A=(A_1, A_2, \dots, A_N) $ of length $ N $ . You are given $ Q $ queries, which you should process in order. Each query is in one of the following formats: - `1 x y` : Change the value of $ A_x $ to $ y $ . - `2 l r` : Find the value of $ \displaystyle \sum_{1\leq i\leq N} \max(l, \min(r, A_i)) $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ Here, $ \text{query}_i\ (1\leq i\leq Q) $ represents the $ i $ -th query and is given in one of the following formats: > $ 1 $ $ x $ $ y $ > $ 2 $ $ l $ $ r $

Let $ K $ be the number of queries of the second type. Output $ K $ lines. The $ i $ -th line ( $ 1\leq i \leq K $ ) should contain the answer to the $ i $ -th query of the second type.

### Sample Explanation 1 Initially, $ A=(4,3,2) $ . - First query: Change the value of $ A_1 $ to $ 7 $ . $ A $ becomes $ (7,3,2) $ . - Second query: Output $ \max(3, \min(5, 7))+\max(3, \min(5, 3))+\max(3, \min(5, 2))=5+3+3=11 $ . - Third query: Change the value of $ A_2 $ to $ 0 $ . $ A $ becomes $ (7,0,2) $ . - Fourth query: Output $ \max(4, \min(2, 7))+\max(4, \min(2, 0))+\max(4, \min(2, 2))=4+4+4=12 $ . ### Constraints - $ 1\leq N \leq 5\times 10^5 $ - $ 1\leq Q \leq 2\times 10^5 $ - $ 0\leq A_i \leq 5\times 10^5 $ - For queries of the first type, - $ 1\leq x\leq N $ - $ 0\leq y \leq 5\times 10^5 $ - For queries of the second type, - $ 0\leq l,r \leq 5\times 10^5 $ - All inputs are integers.