#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=9e18;
const int N=5e5+5;
int n,m,a[N];
struct segment_tree{
	int prefix,suffix,val,sum;
}t[N<<2];
void build(int p,int l,int r){
	t[p].prefix=-inf;
	t[p].suffix=-inf;
	t[p].val=-inf;
	if(l==r){
		t[p].val=a[l];
		t[p].sum=a[l];
		t[p].prefix=a[l];
		t[p].suffix=a[l];
		return;
	}
	int lson=p<<1,rson=p<<1|1,mid=l+(r-l)/2;
	build(lson,l,mid);
	build(rson,mid+1,r);
	t[p].sum=t[lson].sum+t[rson].sum;
	t[p].val=t[lson].suffix+t[rson].prefix;
	t[p].prefix=max(t[lson].prefix,t[lson].sum+t[rson].prefix);
	t[p].suffix=max(t[rson].suffix,t[rson].sum+t[lson].suffix);
}
void update(int p,int l,int r,int x,int val){
	if(l==r&&l==x){
		t[p].val=val;
		t[p].sum=val;
		t[p].prefix=val;
		t[p].suffix=val;
		return;
	}
	int lson=p<<1,rson=p<<1|1,mid=l+(r-l)/2;
	if(x<=mid) update(lson,l,mid,x,val);
	else update(rson,mid+1,r,x,val);
	t[p].sum=t[lson].sum+t[rson].sum;
	t[p].prefix=max(t[lson].prefix,t[lson].sum+t[rson].prefix);
	t[p].suffix=max(t[rson].suffix,t[rson].sum+t[lson].suffix);
	t[p].val=max(t[lson].suffix+t[rson].prefix,max(t[lson].val,t[rson].val));
}
segment_tree query(int p,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return t[p];
	int lson=p<<1,rson=p<<1|1,mid=l+(r-l)/2;
	if(qr<=mid) return query(lson,l,mid,ql,qr);
	else if(ql>mid) return query(rson,mid+1,r,ql,qr);
	else{
		segment_tree res,ltree=query(lson,l,mid,ql,qr),rtree=query(rson,mid+1,r,ql,qr);
		res.sum=ltree.sum+rtree.sum;
		res.prefix=max(ltree.prefix,ltree.sum+rtree.prefix);
		res.suffix=max(rtree.suffix,rtree.sum+ltree.suffix);
		res.val=max(ltree.suffix+rtree.prefix,max(ltree.val,rtree.val));
		return res;
	}
}
signed main(){
	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,1,n);
	while(m--){
		int op; cin>>op;
		if(op==1){
			int l,r; cin>>l>>r;
			cout<<query(1,1,n,l,r).val<<"\n";
		}else{
			int p,s; cin>>p>>s;
			update(1,1,n,p,s);
		}
	}
	return 0;
}