#include<bits/stdc++.h>
using namespace std;
struct os{
	int ln=-1e9,rn=-1e9,n=-1e9,l=2,r=1;
};
struct node{
	int l,r,n,ln,rn;
};
node tree[2000010];
int a[500010],p,x,y;
void build(int p,int l,int r){
	tree[p].l=l;
	tree[p].r=r;
	if (l==r) {
		tree[p].n=a[l];
		tree[p].ln=a[l];
		tree[p].rn=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].ln=max(tree[p*2].ln,a[tree[p*2].r]-a[tree[p*2].l-1]+tree[p*2+1].ln);
	tree[p].rn=max(tree[p*2+1].rn,a[tree[p*2+1].r]-a[tree[p*2+1].l-1]+tree[p*2].rn);
	tree[p].n=max(max(tree[p*2].n,tree[p*2+1].n),tree[p*2].rn+tree[p*2+1].ln);
	return;
}
void update(int s,int p){
	if (p==s) return;
	int mid=(tree[p].l+tree[p].r)/2;
	if (tree[s].l<=mid) update(s,p*2);
	else if (tree[s].l>mid) update(s,p*2+1);
	tree[p].ln=max(tree[p*2].ln,a[tree[p*2].r]-a[tree[p*2].l-1]+tree[p*2+1].ln);
	tree[p].rn=max(tree[p*2+1].rn,a[tree[p*2+1].r]-a[tree[p*2+1].l-1]+tree[p*2].rn);
	tree[p].n=max(max(tree[p*2].n,tree[p*2+1].n),tree[p*2].rn+tree[p*2+1].ln);
	return;
}
os search(int l,int r,int p){
	os t;
	if (tree[p].l==l&&r==tree[p].r) {
		t.n=tree[p].n;
		t.ln=tree[p].ln;
		t.rn=tree[p].rn;
		t.l=tree[p].l;
		t.r=tree[p].r;
		return t;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	os L,R;
	if (l<=mid) L=search(l,min(r,mid),p*2);
	if (r>mid) R=search(max(l,mid+1),r,p*2+1);
	t.l=L.l;
	t.r=R.r;
	t.ln=max(L.ln,a[L.r]-a[L.l-1]+R.ln);
	t.rn=max(R.rn,a[R.r]-a[R.l-1]+L.rn);
	t.n=max(max(L.n,R.n),L.rn+R.ln);
	return t;
}
void change(int x,int y,int s){
	if (tree[s].l==x&&x==tree[s].r){
		tree[s].n=y;
		tree[s].ln=y;
		tree[s].rn=y;
		update(s,1);
		return;
	}
	int mid=(tree[s].l+tree[s].r)/2;
	if (x<=mid) change(x,y,2*s);
	else if (x>mid) change(x,y,2*s+1);
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++) {
		cin>>a[i];
	}
	build(1,1,n);
	for (int i=1;i<=n;i++){
		a[i]=a[i]+a[i-1];
	}
	while (m--)
	{
		cin>>p>>x>>y;
		if (p==1) {
			if (x>y) swap(x,y);
			os t=search(x,y,1);
			cout<<t.n<<'\n';
		}
		else change(x,y,1);
	}
	return 0; 
}