#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[500005];
struct segment_tree{
	int l,r;
	int suml,sumr,sum,tot;
}t[500005];
void pushup(int p){
	t[p].tot=t[p*2].tot+t[p*2+1].tot;
	t[p].suml=max(t[p*2].suml,t[p*2].tot+t[p*2+1].suml);
	t[p].sumr=max(t[p*2+1].sumr,t[p*2+1].tot+t[p*2].sumr);
	t[p].sum=max(t[p*2].sum,max(t[p*2+1].sum,t[p*2].sumr+t[p*2+1].suml));
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].tot=a[l];
		t[p].suml=t[p].sumr=a[l];
		t[p].sum=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
void change(int p,int k,int x){
	if(t[p].l==t[p].r){
		t[p].sum=x;
		t[p].suml=t[p].sumr=t[p].tot=x;
		return ;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(k<=mid) change(p*2,k,x);
	else change(p*2+1,k,x);
	pushup(p);
}
segment_tree query(int p,int l,int r){
	//if(t[p].r<l|t[p].l>r) return 0x3f3f3f3f;
	if(l<=t[p].l&&t[p].r<=r){
		return t[p];
	}
	int mid=(t[p].l+t[p].r)>>1;
	segment_tree t,rt,lt;
	if(r<=mid) return query(p*2,l,r);
	if(l>mid) return query(p*2+1,l,r);
	lt=query(p*2,l,r);
	rt=query(p*2+1,l,r);
	t.suml=max(lt.suml,lt.tot+rt.suml);
	t.sumr=max(rt.sumr,rt.tot+lt.sumr);
	t.sum=max(rt.sum,max(lt.sum,lt.sumr+rt.suml));
	return t;
}
int opt,g,h;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>opt>>g>>h;
		if(opt==2){
			if(g>h) swap(g,h);
			change(1,g,h);
		}
		else{
			if(g>h) swap(g,h);
			cout<<query(1,g,h).sum<<endl;
		}
	}
	return 0;
}