Description
You are given a sequence A of N (N <= 200000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 200000) operations:
modify the i-th element in the sequence or for given x y print max{Ai+ Ai+1+ .. + Aj | x<=i<=j<=y }.
n 个数，q 次操作
操作0 x y把 Ax 修改为y
操作1 l r询问区间 [l,r] 的最大子段和
Input
The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
Output
For each query, print an integer as the problem required.
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3