#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,a[N];
int op,x,y;
struct node{
	int sum,w;
	int lmx,rmx;
}t[4*N];
void pushup(int u){
	t[u].w=t[u*2].w+t[u*2+1].w;
	t[u].lmx=max(t[u*2].lmx,t[u*2].w+t[u*2+1].lmx);
	t[u].rmx=max(t[u*2+1].rmx,t[u*2+1].w+t[u*2].rmx);
	t[u].sum=max(t[u*2].sum,t[u*2+1].sum);
	t[u].sum=max(t[u].sum,t[u*2].sum+t[u*2+1].sum);
}
void build(int u,int l,int r){
	if(l==r){
		t[u].lmx=t[u].rmx=a[l];
		t[u].sum=t[u].w=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	pushup(u);
}
void upd(int u,int l,int r,int p,int x){
	if(l==r){
		t[u].lmx=t[u].rmx=x;
		t[u].sum=t[u].w=x;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid)upd(u*2,l,mid,p,x);
	else upd(u*2+1,mid+1,r,p,x);
	pushup(u);
}
node qry(int u,int L,int R,int l,int r){
	if(l<=L&&R<=r)return t[u];
	int mid=(L+R)>>1;
	if(r<=mid)return qry(u*2,L,mid,l,r);
	else if(mid<l)return qry(u*2+1,mid+1,R,l,r);
	node t,t1,t2;
	t1=qry(u*2,L,mid,l,r);
	t2=qry(u*2+1,mid+1,R,l,r);
	t.lmx=max(t1.lmx,t1.w+t2.lmx);
	t.rmx=max(t2.rmx,t2.w+t1.rmx);
	t.sum=max(max(t1.sum,t2.sum),(t2.lmx+t1.rmx));
	return t;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		cin>>op>>x>>y;
		if(op==1){
			if(x>y)swap(x,y);
			cout<<qry(1,1,n,x,y).sum<<"\n";
		}
		else upd(1,1,n,x,y);
	}
	return 0;
}