U162454 【PKUSC2021】逛街（就当是这个吧）

九条可怜是珂爱的女孩子，当然有职阶技能——逛街啦（背景就别在意了）。

一条街上有$n$个连续的店，可怜对于每个店的喜爱程度不同，具体来说，每个店有一个**不同**的喜爱系数$a_i$。 可怜会在一个连续的$[l,r]$的区间内逛街(顺序不能改变)，可怜初始承受下限为$0$，当可怜走到一家商店$i$时，若这个商店的喜爱系数$a_i$严格大于可怜的承受下限，则可怜会在这个商店买东西并获得$a_i$的收益，且可怜的承受下限会更新为$a_i$。 同时，当商店老板听说可怜要来逛街时大喜过望，他们都希望可怜能来他们的店里买东西，所以他们想办法搞到了可怜对隔壁商店和自己的喜爱程度，所以经常会有模仿的情况出现，但并不是所有商店都参与模仿，但一定是一个连续区间，具体来说，我们说$[l,r]$进行了一次模仿，说明$[l,r)$的商店的喜爱程度全都变为$\max(a_i,a_{i+1})$,现在可怜想知道每次逛街她能获得的收益，快来帮帮她吧。

第一行两个整数$n,m$，表示商店总数与操作个数 接下来一行$n$个整数，表示初始可怜对每个商店的喜爱程度 接下来$m$行，每行$3$个整数$mode,l,r$表示一次操作，$mode$为$1$表示模仿操作，$mode$为$2$表示可怜在逛街，$l,r$为操作对应的区间

对于每个2操作，输出一行一个整数表示可怜这次逛街的收益

#### 样例一解释： 初始喜爱程度为$\{1,3,2,4,5\}$ 第一次询问区间$[1,5]$，可怜会逛第$1,2,4,5$个商店并获得$13$的收益 第一次模仿后喜爱程度为$\{3,3,4,4,5\}$ 第二次询问区间$[1,5]$，可怜会逛第$1,3,4$个商店并获得$12$的收益 第一次模仿后喜爱程度为$\{3,3,5,5,5\}$ 第二次询问区间$[1,5]$，可怜会逛第$1,3$个商店并获得$8$的收益 $Subtask1(7pts):n,m\le3000$ $Subtask2(39pts):对于所有1操作，l=1,r=n$ $Subtask3(54pts):n,m\le100000$