Long Walk

sajib_only Replay of Father Timm Mem...
Limits 1s, 512 MB

One day Rupun the Rabit had a weird idea to go on a walk. She wants to go on a walk in one direction. Then she will walk in some other direction. Then She will walk some other direction. Then she will walk such a way that she returns to the exact place where she had started. But she cannot walk randomly. And she also wants to meet some conditions. But she is feeling lazy and so asked you to help her.

You will be given an array AA. Rupun will give you QQ operations to perform, each of which will be a query or an update.

In each query, Rupun will give you a range of a subarray of AA. You will have to choose 4 values from that array so that:

  1. Rupun can use those values as length of walks.
  2. The total length of walk is maximum possible.
  3. Rupun should be able to walk so that no two path of walk should intersect except for the starting and ending point.

In each update, Rupun will give you 2 integers xx and yy. You have to update the xx-th value of AA with yy, A[x]=yA[x] = y. (1-indexed)

You have to output the maximal total length of walk (Sum of the length of the four walks).

Input

The first line of input contains two integers, NN and QQ (1N,Q5×1041 ≤ N,Q ≤ 5 \times 10^4).

Next line will contain NN integers of the array AA (1A[i]1091 ≤ A[i] ≤ 10^9).

Each of the next QQ lines contain 3 integers, tt, xx and yy.

If tt is 0, then it is a query operation. You have to answer the query for the range A[x],A[x+1],...,A[y]A[x], A[x+1], ..., A[y]. If it is impossible to choose 4 values meeting the above conditions, then the answer is 0. (1xyN1 ≤ x ≤ y ≤ N)

If tt is 1, then it is an update operation. You have to make the update, A[x]=yA[x] = y. (1xN1 ≤ x ≤ N and 1y1091 ≤ y ≤ 10^9)

Output

For each query, print the answer in each line.

Samples

InputOutput
15 5
1 15 1 1 14 6 17 20 3 20 14 4 1 15 2 
0 1 7
1 7 9
0 7 14
0 11 15
1 8 18
52
69
35
InputOutput
15 5
12 18 19 19 10 12 14 11 16 2 16 1 18 13 3 
0 12 15
0 6 13
0 10 14
0 2 15
0 4 8
0
64
49
74
56

Submit

Login to submit.

Statistics

33% Solution Ratio
fsshakkhorEarliest, Nov '20
fsshakkhorFastest, 0.4s
fsshakkhorLightest, 12 MB
fsshakkhorShortest, 4319B
Toph uses cookies. By continuing you agree to our Cookie Policy.