#include<bits/stdc++.h>
using namespace std;
struct ghj{
	int l,r;
	long long ans,ansl,ansr,cnt;
}tree[2000009];
int n,m,a[500009],op,x,l,r,d;
void push_up(int q){
	tree[q].cnt=tree[q*2].cnt+tree[q*2+1].cnt;
	tree[q].ansl=max(tree[q*2].ansl,tree[q*2].cnt+tree[q*2+1].ansl);
	tree[q].ansr=max(tree[q*2+1].ansr,tree[q*2+1].cnt+tree[q*2].ansr);
	tree[q].ans=max(max(tree[q*2].ans,tree[q*2+1].ans),tree[q*2].ansr+tree[q*2+1].ansl);
}
void build(int l,int r,int p=1){
	tree[p].l=l;
	tree[p].r=r;
	if(l==r){
		cin>>tree[p].cnt;
		tree[p].ansl=tree[p].ansr=tree[p].ans=tree[p].cnt;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
	push_up(p);
}
void update(int x,int d,int p=1){
	if(tree[p].l==tree[p].r){
		tree[p].cnt=d;
		tree[p].ansl=d;
		tree[p].ansr=d;
		tree[p].ans=d;
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	if(x<=mid) update(x,d,p*2);
	else update(x,d,p*2+1);
	push_up(p);
}
ghj query(int p,int l,int r){
	if(l<=tree[p].l && tree[p].r<=r) return tree[p];
	int mid=(tree[p].l+tree[p].r)/2;
	if(r<=mid) return query(p*2,l,r);
	else{
		if(r>mid) return query(p*2+1,l,r);
		else{
			ghj t,a=query(p*2,l,r),b=query(p*2+1,l,r);
			t.ansl=max(a.ansl,a.cnt+b.ansl);
			t.ansr=max(b.ansr,a.ansr+b.cnt);
			t.ans=max(max(a.ans,b.ans),a.ansr+b.ansl);
			return t;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	build(1,n,1);
	while(m--){
		cin>>op;
		if(op==1){
			cin>>l>>r;
			if(l>r)swap(l,r);
			cout<<query(1,l,r).ans<<'\n';
		}
		else{
			cin>>x>>d;
			update(x,d);
		}
	}
}