题目描述

轨道上有若干地铁，这里我们将地铁抽象为小球，将轨道抽象为数轴。

有若干个小球放在数轴上，第 $i$ 号小球的坐标参数为 $a_i$。

有两种操作：

1.输入 $i, v$ ，修改第 i 号小球的坐标参数为 $a_i \leftarrow v$；

2.输入 $l, r$，询问下述内容：

按照 $a_i$ 从小到大的顺序（$a_i$ 相等时按 $i$ 从小到大的顺序）依次将小球放在数轴上。

第 $i$ 号小球放在 $\leq a_i$ 的没有被之前放置的小球占据的最大的整点处，设第 $i$ 号小球放置的位置为 $b_i$。

请你输出 $\sum_{i=1,2,\cdots,n,[l,r]\subseteq[b_i,a_i]}(a_i + b_i)$ 的值。也即，所有满足 $b_i \leq l, a_i \geq r$ 的小球的 $a_i + b_i$ 之和。

输入格式

第一行两个正整数 $n, q$ ，分别表示小球个数和操作次数。

第二行 $n$ 个整数 $a_1, a_2,\cdots, a_n$ ，用空格分隔，表示初始的坐标参数。

接下来 $q$ 行每行是下列两种之一：

1 i v 表示修改第 i 号小球的坐标参数为 $a_i \leftarrow v$；

2 l r 表示询问 $\sum_{i=1,2,\cdots,n,[l,r]\subseteq[b_i,a_i]}(a_i + b_i)$

对于每种操作 2 ，输出一行一个整数表示答案。

最开始，三个小球的位置依次为：

1.$b_1 = 5, a_1 = 5$；

2.$b_2 = 4, a_2 = 5$；

3.$b_3 = 3, a_3 = 5$。

修改之后，三个小球的位置依次为：

1.$b_2 = 4, a_2 = 4$；

2.$b_1 = 5, a_1 = 5$；

3.$b_3 = 3, a_3 = 5$。

见下发文件，样例约束与子任务 1 相同。

对于所有数据，$1 \leq n \leq 10^5, 1 \leq q \leq 2 \times 10^5, n < a_i, v \leq 2n, 1 \leq l \leq r \leq 2_n$。