#include<bits/stdc++.h>
using namespace std;
int n,m,a[500000];
struct node{
	int Max,Maxl,Maxr,sum;
}t[2000010];
void pushup(int id){
	t[id].sum=t[id<<1].sum+t[(id<<1)|1].sum;
	t[id].Maxl=max(t[id<<1].Maxl,t[id<<1].sum+t[(id<<1)|1].Maxl);
	t[id].Maxr=max(t[(id<<1)|1].Maxr,t[id<<1].Maxr+t[(id<<1)|1].sum);
	t[id].Max=max({t[id<<1].Max,t[(id<<1)|1].Max,t[id<<1].Maxr+t[(id<<1)|1].Maxl});
}
void build(int l,int r,int id){
	if(l==r){
		t[id].Max=t[id].Maxl=t[id].Maxr=t[id].sum=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,id<<1),build(mid+1,r,(id<<1)|1);
	pushup(id);
}
void modify(int l,int r,int x,int v,int id){
	if(l>x||r<x)
		return ;
	if(l==x&&r==x){
		t[id].Max=t[id].Maxl=t[id].Maxr=t[id].sum=v;
		return ;
	}
	int mid=(l+r)>>1;
	modify(l,mid,x,v,id<<1),modify(mid+1,r,x,v,(id<<1)|1);
	pushup(id);
}
node query(int l,int r,int ql,int qr,int id){
	if(l>=ql&&r<=qr)
		return t[id];
	int mid=(l+r)>>1;
	if(qr<=mid)
		return query(l,mid,ql,qr,id<<1);
	else if(ql>mid)
		return query(mid+1,r,ql,qr,(id<<1)|1);
	else{
		node x=query(l,mid,ql,qr,id<<1),y=query(mid+1,r,ql,qr,(id<<1)|1);
		node ans={max({x.Max,y.Max,x.Maxr+y.Maxl}),max(x.Maxl,x.sum+y.Maxl),max(y.Maxr,y.sum+x.Maxr),x.sum+y.sum};
		return ans;
	}
}
int main(){
//	freopen("P4513_7.in","r",stdin);
//	freopen("P4513_7.ans","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,n,1);
	while(m--){
		int op;
		cin>>op;
		if(op==1){
			int a,b;
			cin>>a>>b;
			if(a>b)
				swap(a,b);
			cout<<query(1,n,a,b,1).Max<<"\n";
		}
		else{
			int x,v;
			cin>>x>>v;
			modify(1,n,x,v,1);
		}
	}
}