作为一名程序员，可怜最困难的时候就和她的好朋友 Sylvia 逛街的时候。
可怜她们常去的商场有 $n$ 家服装店，编号从 $1$ 到 $n$。在可怜的审美中，每一家服装店的服饰都有一个美观度。在最开始的时候，第 $i$ 家店里服饰的美观度是 $x_i$。可怜不喜欢模棱两可，因此 $x_i$ 是两两不同的。
可怜有着特殊的逛街技巧：每次逛街的时候，可怜都会选择一个编号的区间 $[l,r]$，并依次进入编号为 $l, l+1, \dots, r$ 的店。最开始的时候，可怜对于美观度的承受下限是 $0$。每当进入一家新的店，如果这家店服饰的美观度严格大于可怜的承受下限，那么可怜就会购买这家店的服饰，同时可怜的承受下限将会变成这家店服饰的美观度。否则，可怜不会在这家店里购买任何东西。可怜一次逛街的收益等于她购买的所有服饰的美观度之和。
俗话说得好，天下文章一大抄：服装店也不例外。有些时候，一些服装店会模仿他们竞争对手的设计。每一次模仿事件都发生在编号连续的一些店面中（假设是区间 $[l,r]$，同时假设在模仿之前，第 $i$ 家店服饰的美观度是 $a_i$）。最开始，第 $l$ 家店模仿了第 $l+1$ 家店，他的美观度从 $a_l$ 变成了 $\max(a_l,a_{l+1})$。接着，内卷的锁链就开始了，当第 $l+1$ 家店发现自己被模仿了之后，为了保证竞争力，他会去模仿编号为 $l+2$ 的店面，于是他的美观度变成了 $\max(a_{l+1},a_{l+2})$。这样的过程一直持续到第 $r$ 家店被模仿的时候：因为第 $r$ 家店选择了保持不变，所以内卷的锁链就结束了。
简单来说，对于一次发生在区间 $[l,r]$ 中的模仿事件，假设在事件发生前，第 $i$ 家店的美观度是 $a_i$，那么在事件发生后，对于 $[l,r)$ 中的每一家店 $i$，他的美观度都会变成 $\max(a_i,a_{i+1})$；对于其他的所有店，他们的美观度都保持不变。
现在，按照时间顺序发生了 $m$ 个事件，事件有两种：
- 模仿事件 $1$ $l$ $r$，表示在区间 $[l,r]$ 中，发生了一次模仿事件。
- 逛街事件 $2$ $l$ $r$，表示可怜选择区间 $[l,r]$ 逛了一次街。
你需要在每次逛街事件的时候，输出可怜的收益。
输入格式
输入第一行包含两个整数 $n,m (1 \leq n,m \leq 3 \times 10^5)$，表示店面的数量以及事件个数。
第二行包含 $n$ 个整数 $x_i (1 \leq x_i \leq 10^9)$，表示最开始的时候，每一家店的美观度。
接下来 $m$ 行，每行包含三个整数 $t, l, r (t \in \{1,2\}, 1 \leq l < r \leq n)$，描述了一个事件。
输入保证数组 $x$ 中的元素两两不同。
输出格式
对于每一次逛街事件，输出一行一个整数，表示可怜的收益。
样例数据
样例输入
5 5 1 3 2 4 5 2 1 5 1 1 5 2 1 5 1 3 4 2 1 5
样例输出
13 12 8
样例解释
下面是对样例数据的解释：
- 可怜在逛街的时候会选择编号为 1,2,4,5 的商店购买服饰，因此收益为 13。
- 在模仿事件发生之后，商店的美观度变成了 3,3,4,5,5。
- 可怜会选择编号为 1,3,4 的商店购买服饰，因此收益为 12。
- 在模仿事件发生之后，商店的美观度变成了 3,3,5,5,5。
- 可怜会选择编号为 1,3 的商店购买服饰，因此收益为 8。
子任务
子任务一（$7$ 分），$1 \leq n,m \leq 5 \times 10^3$。
子任务二（$39$ 分），输入保证在 $t = 1$ 的时候，$l = 1, r= n$。
子任务三（$54$ 分），$1 \leq n ,m \leq 3 \times 10^5$。