Background

Shizuha Aki is the goddess who manages falling leaves in autumn. When autumn is about to end, due to her power, the mountains will turn completely fiery red. At the same time, turning red leaves into fallen leaves is also part of her job.

Minoriko Aki is the goddess who manages harvest in autumn. Opposite to Shizuha Aki’s duty, she is in charge of the ripening of autumn fruits and the harvesting of autumn crops.

In an autumn woven with happiness and sorrow, how can one not feel sentimental?

Problem Description

Minoriko Aki and Shizuha Aki are deities in charge of autumn, so they control the harvest of the fields. Specifically, there are $n$ fields arranged in order, and the harvest level of the $i$-th field is $a_i$. The Aki sisters will use this to determine how good the year’s harvest is.

After considering various factors, the Aki sisters determined that harvesting fields $l$ through $r$ yields a total crop amount $\Omega(l,r)$. It is defined as follows:

$$\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}$$

There is an explanation of the related symbols in the Hint section.

---

Due to certain factors, the harvest levels of the fields will change. Therefore, the Aki sisters will perform $q$ operations on $a$:

1. In the form $\colorbox{f0f0f0}{\verb!1 x y!}$, meaning to add $y$ to $a_1,a_{2},a_{3},\cdots ,a_x$ respectively.
2. In the form $\colorbox{f0f0f0}{\verb!2 l r!}$, meaning to query the value of $\Omega(l,r)$.

Input Format

• The first line contains two positive integers $n,q$, representing the total number of fields and the number of operations.
• The next line contains $n$ integers, representing the harvest level of each field.
• The next $q$ lines: the first number $op$ indicates the type of the operation.
  • If $op=1$, then two integers $x,y$ follow, with the meaning as described.
  • If $op=2$, then two positive integers $l,r$ follow, with the meaning as described.

Output Format

• Output several lines. For each operation $2$, output the corresponding result.

6 3
1 1 4 5 1 4
2 3 5
1 2 5
2 3 5

0
1

10 6
1 3 5 7 8 12 14 15 17 18
2 5 9
1 3 10
2 4 5
1 1 10
2 4 6
2 1 10

0
1
3
0

Hint

Sample $3$ can be found in the attached files $\textbf{\textit{sequence3.in}}/\textbf{\textit{sequence3.ans}}$.

Constraints and Conventions

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,q\le} & \textbf{Special Property} & \textbf{Score}\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}$$

Special Property $\textbf{A}$: It is guaranteed that for any $i\in[1,n-1]$, we have $a_i<a_{i+1}$.
Special Property $\textbf{B}$: It is guaranteed that there is no operation $1$.

For all testdata, it is guaranteed that $1 \leq n,q \leq 6\times10^6$, $a_i,y_i\in[0,10^9]$, $1\le x_i\le n$, and $1\le l_i\le r_i \le n$.

Symbol Explanation

• $[P]$ is the Iverson bracket, where $P$ is a condition. If $P$ is true, then the value of the expression is $1$; otherwise it is $0$. That is,

$$[P]=\begin{cases}1 & \text{$P$ is true}\cr 0 & \text{$P$ is false}\end{cases}$$

• $\min\limits_{i=l}^r\{P\}$ denotes the minimum value of the expression $P$ when $i$ takes $l,l+1,l+2,\cdots,r$. Similarly, $\max\limits_{i=l}^r\{P\}$ is defined.

Additional Hint

The input and output size of this problem is large, so please pay attention to the impact of constant factors.

Translated by ChatGPT 5