DerrickLo's Attribute Equalization Problem

In DerrickLo's game, there are ( n ) attributes, where the ( i )-th attribute has an initial value ( a_i ). You will be given ( q ) operations. Each operation is one of the following types:

1. Modification Operation:

   ( 1; k; x )

   Set ( a_k ) to ( x ).

2. Query Operation:

   ( 2; l; r )

   Compute the minimum cost to make all attributes in the subarray ( [l, r] ) equal by simulating (but not actually executing) only the following two operations:

   a. Increase Operation: Choose an index ( p ) and increase ( a_p ) by ( 1 ) at a cost of ( 1 ) per increment.

   b. Range Maximum Operation: Choose a contiguous interval ( [x,y] ) and set every element ( a_i ) (for ( x \le i \le y )) equal to ( \max_{i=x}^{y}a_i ) at a cost of ( (y-x+1)^2 ).

For the purpose of the query, assume that the final value to which all elements in ( [l, r] ) are equalized is the initial maximum ( M = \max{a_l, a_{l+1}, \ldots, a_r} ). You may increase values (via the increase operation) and use a range maximum update as many times as needed. The cost for a contiguous segment when equalizing is the minimum between increasing each element individually (which costs ( \sum_{i=l}^{r}(M - a_i) )) and applying a range maximum operation followed by necessary increases (which costs ( (\text{length})^2 + (\text{length})\times(M - m_{segment}) ), where ( m_{segment} ) is the maximum value in that subsegment before the operation).

Your task is to process all ( q ) operations and, for each query, output the minimum total cost needed to equalize the corresponding subarray.

inputFormat

The first line contains two integers ( n ) and ( q ) -- the number of attributes and the number of operations.

The second line contains ( n ) integers: ( a_1, a_2, \ldots, a_n ), representing the initial values of the attributes.

Each of the next ( q ) lines describes an operation in one of the following formats:

• 1 k x — Modification Operation. Set ( a_k ) to ( x ).

• 2 l r — Query Operation. Compute and output the minimum cost to equalize the attributes in the interval ( [l, r] ) as described above.

outputFormat

For each query operation (i.e. lines starting with 2), output a single integer representing the minimum cost required to equalize the attributes in the given range.

sample

3 3
1 2 3
2 1 3
1 2 3
2 1 3

3
1