问题 H: Mountain View

链接：https://ac.nowcoder.com/acm/contest/57361/H
来源：牛客网
You enjoy the mountain view, especially on a rainy day.

For a positive integer sequence b1,b2,⋯,bk(k≥2)b_1,b_2,\cdots, b_k(k \geq 2)b1,b2,⋯,bk(k≥2), you define its beauty as following:

Suppose there is a broken line connecting (1,b1),(2,b2),⋯,(k,bk)(1, b_1), (2, b_2), \cdots, (k, b_k)(1,b1),(2,b2),⋯,(k,bk) one by one on the Cartesian plane, representing a mountain's outline. To the immediate right of (k,bk)(k, b_k)(k,bk) is a vertical cliff whose height can be assumed infinite (but to the left of (1,b1)(1, b_1)(1,b1) there isn't). Small ponds form on rainy days, and the beauty is the maximum ponding area on this 2D graph.



Now you have an integer sequence a1,a2,⋯,ana_1, a_2, \cdots, a_na1,a2,⋯,an. Support two operations:

• `1 x y` — Set axa_xax to $y$.
• `2 l r` — Print the beauty of al,al+1,⋯,ara_l, a_{l+1}, \cdots, a_ral,al+1,⋯,ar.

The first line contains two integers $n$ and $q$ (2≤n≤1052 \leq n \leq 10^52≤n≤105, 1≤q≤1051 \leq q \leq 10^51≤q≤105).
The second line contains $n$ integers: the initial values of a1,a2,⋯,ana_1, a_2, \cdots, a_na1,a2,⋯,an (1≤ai≤1091 \leq a_i \leq 10^91≤ai≤109).
The next $q$ lines each contain three integers, representing the operations. It is guaranteed that $1\le x\le n$, 1≤y≤1091\leq y \leq 10^91≤y≤109, 1≤l<r≤n1 \leq l < r \leq n1≤l<r≤n.

Print the answer for each query. The answer may not be an integer, so your output will be considered correct if its absolute or relative error does not exceed 10−910^{-9}10−9.

9 5
1 4 2 3 1 5 3 6 5
2 1 9
1 5 3
2 4 6
2 2 7
2 1 8

7.791666666667
0.000000000000
4.750000000000
5.416666666667

The blue area of the image in the statement demonstrates the first query of the first sample.