C. Triangles
time limit per test
4 s
memory limit per test
512 megabytes
input
standard input
output
standard output

In the geometry class, Ulugbek learned about the triangle inequality. For three sticks of length $$$x$$$, $$$y$$$, and $$$z$$$ meters, the following properties should be held: $$$x+y \gt z$$$, $$$x+z \gt y$$$, and $$$y+z \gt x$$$. The perimeter of this triangle equals $$$x+y+z$$$ meters.

There are $$$n$$$ sticks of length $$$a[0], a[1], \ldots, a[n-1]$$$ meters. Ulugbek gives you $$$q$$$ queries of two types:

  • $$$0 \; p \; v$$$ — set $$$a[p] := v$$$
  • $$$1 \; l \; r$$$ — find the triangle with the largest perimeter if you can only use sticks in the range $$$[l, r]$$$, i.e. $$$a[l], a[l + 1], \ldots, a[r]$$$. Each side of the triangle must be created using exactly one stick. Return $$$0$$$ if you can't make any triangles.
Input

The first line contains $$$n$$$ and $$$q$$$. ($$$1 \le n, q \le 2 \cdot 10^5$$$)

The second line contains $$$a[0], a[1], \ldots, a[n-1]$$$. ($$$1 \le a[i] \le 5 \cdot 10^8$$$).

The next $$$q$$$ lines contain queries of either type $$$0 \; p \; v$$$ or $$$1 \; l \; r$$$. ($$$0 \le p \le n - 1$$$, $$$1 \le v \le 5 \cdot 10^8$$$), ($$$0 \le l \le r \le n - 1$$$).

Output

For each query of type $$$1 \; l \; r$$$, print the largest possible perimeter using sticks in the range $$$[l, r]$$$, or print $$$0$$$ if it is impossible to create a triangle.

Scoring
GroupAdd. constraintsPoints
$$$0$$$examples$$$0$$$
$$$1$$$$$$n, q \le 80$$$$$$3$$$
$$$2$$$$$$n, q \le 400$$$$$$7$$$
$$$3$$$$$$n, q \le 3000$$$$$$16$$$
$$$4$$$All values of $$$a[i]$$$ and $$$v$$$ are integer powers of $$$2$$$.$$$15$$$
$$$5$$$There are no queries of type $$$0 \; p \; v$$$$$$16$$$
$$$6$$$$$$a[i], v \le 10^5$$$$$$20$$$
$$$7$$$$$$n \le 5 \cdot 10^4$$$$$$10$$$
$$$8$$$—$$$13$$$
Example
Input
7 3
3 1 4 1 5 9 2
1 2 6
0 0 7
1 0 2
Output
11
0
Note

For query $$$l=2$$$ and $$$r=6$$$, we can use sticks $$$a[2] = 4$$$, $$$a[4] = 5$$$, and $$$a[6] = 2$$$. The perimeter equals $$$4+5+2=11$$$.

Then, we are asked to set $$$a[0] := 7$$$. Now, $$$a=[7, 1, 4, 1, 5, 9, 2]$$$.

In the next query, $$$l=0$$$ and $$$r=2$$$. The only triplet is $$$(7, 1, 4)$$$, which doesn't follow the triangle inequality. Thus, the answer is $$$0$$$.