Description

There is an array $a$ with $n$ numbers ($1\le n,a_i\le 2\times10^5$). You have to handle $q$ modifications or queries ($1\le q\le 2\times10^5$). There are two types of modifications or queries:

• Input 1 k x, this changes $a_k$ into $x$ ($1\le k\le n$, $1\le x\le 2\times10^5$) (modify).

• Input 2 l r, you have to print the minimum cost of making $a_l\dots a_r$ the same by the two operations below (This does not really changes the array.) ($1\le l\le r\le 2\times 10^5$) (query):

1. Choose an integer $p$, increase $a_p$ by $1$. This costs $1$.

2. Choose an interval $[x,y]$, change $a_x\dots a_y$ into $\max\limits_{i=x}^ya_i$. This costs $(y-x+1)^2$.

Input Format

The first line contains two integers $n,q$.

The second line contains $n$ integers, representing $a$.

For the next $q$ lines, each line contains three integers, representing a modify or a query.

Output Format

Suppose there are $t$ queries. Please output $t$ lines, representing the answers for each one.

3 2
1 2 3
2 1 2
2 1 1

1
0

Hint

For the first query, we choose $a_1$ and increase it by $1$. This costs $1$. So output $1$.

For the second query, we don't need to do any operations since the number in $[1,1]$ is already the same.