#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
	int l,r;
	long long ans,sum,l_max,r_max;
}tree[400005];
int a[100005];
void up(int p)
{
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
	tree[p].l_max=max(tree[p*2].l_max,tree[p*2].sum+tree[p*2+1].l_max);
	tree[p].r_max=max(tree[p*2+1].r_max,tree[p*2+1].sum+tree[p*2].r_max);
	tree[p].ans=(tree[p*2].ans,max(tree[p*2+1].ans,tree[p*2].r_max+tree[p*2+1].l_max));
}
void build(int l,int r,int p)
{
	tree[p].l=l,tree[p].r=r;
	if(l==r)
	{
		tree[p].sum=tree[p].l_max=tree[p].r_max=tree[p].ans=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
	up(p);
}
void update(int p,int idx,int k)
{
	if(tree[p].l==tree[p].r)
	{
		tree[p].sum=tree[p].l_max=tree[p].r_max=tree[p].ans=k;
		return ;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	if(idx<=mid) update(p*2,idx,k);
	else update(p*2+1,idx,k);
	up(p);
}
node query(int p,int l,int r)
{
	if(l<=tree[p].l and r>=tree[p].r) return tree[p];
	int mid=(tree[p].l+tree[p].r)/2;
	if(r<=mid) return query(p*2,l,r);
	else
	{
		if(l>mid) return query(p*2+1,l,r);
		else
		{
			node t,x=query(p*2,l,r),y=query(p*2+1,l,r);
			t.l_max=max(x.l_max,x.sum+y.l_max),t.r_max=max(y.r_max,y.sum+x.r_max);
			t.ans=max(x.ans,max(y.ans,x.r_max+y.l_max));
			return t;
		}
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,n,1);
	while(m--)
	{
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1)
		{
			if(l>r) swap(l,r);
			cout<<query(1,l,r).ans<<endl;
		}
		else update(1,l,r);
	}
	return 0;
}