#include<iostream>
#include<cstdio>
#define N 500010
using namespace std;
int n,m,q[N],tot;
struct Segment_Tree{
	int l,r,sum;
	int Pre_sum;  //---最大前缀和 
	int Last_sum;  //--最大后缀和 
	int Part_sum;  //--最大子段和 
} s[N*4],w[N],ans;
void re(int &x)
{
	int t=0;x=0;char i=getchar();
	if(i=='-') t=1;
	while(i<'0'||i>'9') i=getchar();
	while(i>='0'&&i<='9') x=(x<<1)+(x<<3)+i-'0',i=getchar();
	if(t) x=-x;
}
void build(int p,int l,int r)
{
	s[p].l=l;s[p].r=r;
	if(l==r)
	{
		s[p].sum=q[l];s[p].Pre_sum=q[l];
		s[p].Last_sum=q[l];s[p].Part_sum=q[l];
		return;
	}
	int mid=(l+r)/2;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	s[p].sum=s[p<<1].sum+s[p<<1|1].sum;
	s[p].Pre_sum=max(s[p<<1].Pre_sum,s[p<<1].sum+s[p<<1|1].Pre_sum);
	s[p].Last_sum=max(s[p<<1|1].Last_sum,s[p<<1|1].sum+s[p<<1].Last_sum);
	s[p].Part_sum=max(s[p<<1].Part_sum,max(s[p<<1|1].Part_sum,s[p<<1].Last_sum+s[p<<1|1].Pre_sum));
}
void update(int p,int l,int r,int d)
{
	if(l<=s[p].l&&r>=s[p].r)
	{
		s[p].sum=d;s[p].Pre_sum=d;
		s[p].Last_sum=d;s[p].Part_sum=d;
		return;
	}
	int mid=(s[p].l+s[p].r)/2;
	if(l<=mid) update(p<<1,l,r,d);
	if(r>mid) update(p<<1|1,l,r,d);
	s[p].sum=s[p<<1].sum+s[p<<1|1].sum;
	s[p].Pre_sum=max(s[p<<1].Pre_sum,s[p<<1].sum+s[p<<1|1].Pre_sum);
	s[p].Last_sum=max(s[p<<1|1].Last_sum,s[p<<1|1].sum+s[p<<1].Last_sum);
	s[p].Part_sum=max(s[p<<1].Part_sum,max(s[p<<1|1].Part_sum,s[p<<1].Last_sum+s[p<<1|1].Pre_sum));
}
void query(int p,int l,int r)
{
	if(l<=s[p].l&&r>=s[p].r) {w[++tot]=s[p];return;}
	int mid=(s[p].l+s[p].r)/2;
	if(l<=mid) query(p<<1,l,r);
	if(r>mid) query(p<<1|1,l,r);
}
void solve(Segment_Tree a,Segment_Tree b)
{
	if(a.l>=b.r) swap(a,b);
	ans.l=a.l;ans.r=b.r;
	ans.sum=a.sum+b.sum;
	ans.Pre_sum=max(a.Pre_sum,a.sum+b.Pre_sum);
	ans.Last_sum=max(a.Last_sum+b.sum,b.Last_sum);
	ans.Part_sum=max(a.Part_sum,max(b.Part_sum,a.Last_sum+b.Pre_sum));
}
int main()
{
	freopen("bai.in","r",stdin);
	freopen("bai.out","w",stdout);
	re(n);re(m);
	for(int i=1;i<=n;i++) re(q[i]);
	build(1,1,n);
	int op,x,y;
	for(int i=1;i<=m;i++)
	{
		re(op);re(x);re(y);
		if(op==1)
		{
			if(x>y) swap(x,y);
			tot=0;
			query(1,x,y);ans=w[1];
			for(int i=2;i<=tot;i++) solve(w[i],ans);
			printf("%d\n",ans.Part_sum);
		}
		else update(1,x,x,y);
	}
	return 0;
}