P8010 「Wdsr-3」令人感伤的红雨

秋静叶是在秋季掌管落叶的神明。在秋季即将迎来落幕之时，因她的力量使然，山里会变得火红一片。同时，将红叶变为落叶也是她工作的一环。 秋穰子是在秋季掌管丰收的神明。与秋静叶的职责相反，她掌管着秋天果实的成熟、秋粮的收获。 交织着快乐与忧愁的秋天，怎能让人不有感而发呢？

秋穰子和秋静叶是掌管秋天的神灵，因而控制着田地的收成。具体而言，有 $n$ 块田依次排列，第 $i$ 块田的丰收程度为 $a_i$。秋之姐妹会据此得出一年的年成。 在综合考察了各方面因素后，秋之姐妹得出了收获第 $l$ 块至第 $r$ 块田地可以获得的作物总量 $\Omega(l,r)$。具体定义如下： $$ \begin{aligned} \Alpha(l,r)&=\max_{i=l}^r\{i\times[a_i=\max_{j=l}^r\{a_j\}]\}\cr \Beta(l,r)&=\max_{i=l}^r\{\min_{j=1}^i\{\Alpha(j,i)\}\}-\min_{i=l}^r\{\max_{j=1}^i\{\Alpha(j,i)\}\}\cr \Omega(l,r)&=\min_{i=l}^r\{\min_{j=i}^r\{|\Beta(i,j)|\}\} \end{aligned}$$ 在**提示说明**部分有相关符号的解释。 --- 由于相关因素的影响，田地的丰收程度会发生变化。因此秋之姐妹会对 $a$ 进行 $q$ 次操作： 1. 形如 $\colorbox{f0f0f0}{\verb!1 x y!}$，表示让 $a_1,a_{2},a_{3},\cdots ,a_x$ **分别加上** $y$。 2. 形如 $\colorbox{f0f0f0}{\verb!2 l r!}$，表示询问 $\Omega(l,r)$ 的值。

无

无

样例 $3$ 见下发的附件 $\textbf{\textit{sequence3.in}}/\textbf{\textit{sequence3.ans}}$。 #### 数据范围及约定 $$ \def{\arraystretch}{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,q\le} & \textbf{特殊性质} & \textbf{分值}\cr\hline 1 & 100 & - & 10\cr\hline 2 & 5\times 10^3 & - &15\cr\hline 3 & 10^5 & \text{A} &10\cr\hline 4 & 10^5 & \text{B} &5\cr\hline 5 & 10^5 & - &30\cr\hline 6 & 6\times 10^6 & - & 30\cr\hline \end{array} $$ **特殊性质** $\textbf{A}$：保证对于任意的 $i\in[1,n-1]$，都有 $a_i