You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

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.

Example

Input:
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3

Output:
6
4
-3

思路：

要是由浅入深的话，建议先看一下这篇，一个一个关键点来。https://blog.csdn.net/TherAndI/article/details/122714363https://blog.csdn.net/TherAndI/article/details/122714363然后和Ⅰ相比这就是多了一个单点修改change()，其他的不能说是一模一样，只能说是分毫不差，main()函数当然要改的。

#include<iostream>
using namespace std;
typedef long long ll;
const int N=5e4;
int n,m,ch,x;
ll y;
ll a[N+5];
struct tree
{
	ll sum,ans,lans,rans;
}t[N*4+5];
void pushup(int k)
{
	t[k].sum =t[k*2].sum +t[k*2+1].sum ;
	t[k].lans =max(t[k*2].lans ,t[k*2].sum +t[k*2+1].lans );
	t[k].rans =max(t[k*2+1].rans ,t[k*2+1].sum +t[k*2].rans );
	t[k].ans =max(max(t[k*2].ans ,t[k*2+1].ans ),t[k*2].rans +t[k*2+1].lans );
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		t[k].sum =t[k].ans =t[k].lans =t[k].rans =a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	pushup(k);
}
void change(int k,int l,int r,int x,ll y)
{
	if(l==r&&l==x)
	{
		t[k].ans =t[k].lans =t[k].rans =t[k].sum =y;
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid)
		change(k*2,l,mid,x,y);
	else
		change(k*2+1,mid+1,r,x,y);
	pushup(k);
}
tree query(int k,int l,int r,int x,ll y)
{
	if(x<=l&&y>=r)
		return t[k];
	int mid=(l+r)/2;
	if(y<=mid)
		return query(k*2,l,mid,x,y);
	else if(x>mid)
		return query(k*2+1,mid+1,r,x,y);
	else
	{
		tree re,left,right;
		left=query(k*2,l,mid,x,y);
		right=query(k*2+1,mid+1,r,x,y);
		re.sum =left.sum +right.sum ;
		re.lans =max(left.lans ,left.sum +right.lans );
		re.rans =max(right.rans ,right.sum +left.rans );
		re.ans =max(max(left.ans ,right.ans ),left.rans +right.lans );
		return re;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	build(1,1,n);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d %d %lld",&ch,&x,&y);
		if(ch==1)
		{
			printf("%lld\n",query(1,1,n,x,y).ans );
		}	
		else
		{
			change(1,1,n,x,y);
		}
	}	
	return 0;
}