#include<bits/stdc++.h>
#define NN 500050
typedef long long ll;
using namespace std;
ll m,n;
struct P{
	ll l,r,s,sl,sr,sum;
};
P tr[4*NN];
ll inp[NN];
vector<ll>ans;
void f(ll k){
	tr[k].s=max(tr[2*k].s,tr[2*k+1].s);// 
	tr[k].sl=tr[2*k].sl;
	tr[k].sr=tr[2*k+1].sr;
	tr[k].sum=tr[2*k].sum+tr[2*k+1].sum;
	if(tr[2*k].sr+tr[2*k+1].sl>=tr[k].s){
		tr[k].s=tr[2*k].sr+tr[2*k+1].sl;// 
	}
	tr[k].sl=max(tr[k].sl,tr[2*k].sum+tr[2*k+1].sl);
	tr[k].sr=max(tr[k].sr,tr[2*k+1].sum+tr[2*k].sr);
	tr[k].s=max(tr[k].s,tr[k].sl);//
	tr[k].s=max(tr[k].s,tr[k].sr);//
}
void build(ll k,ll l,ll r){
	tr[k].l=l;
	tr[k].r=r;
	if(l==r){
		tr[k].s=inp[l];
		tr[k].sl=inp[l];
		tr[k].sr=inp[l];
		tr[k].sum=inp[l];
	}else{
		build(2*k,l,(l+r)/2);
		build(2*k+1,(l+r)/2+1,r);
		f(k);
	}
}
void change(ll k,ll x,ll y){
	ll L=tr[k].l;
	ll R=tr[k].r;
	if(L==R && L==x){
		tr[k].s=y;
		tr[k].sum=y;
		tr[k].sl=y;
		tr[k].sr=y;
	}else{
		ll mid=(L+R)/2;
		if(mid>=x){
			change(2*k,x,y);
		}else{
			change(2*k+1,x,y);
		}
		f(k);
	}
}

ll ask(ll k,ll l,ll r,ll isl){
	ll L=tr[k].l;
	ll R=tr[k].r;
	if(isl){//右往左逼近 
		if(R<=r){//直到满足条件 
			return tr[k].sl;
		}else{
			return ask(2*k,l,r,isl);
		}
	}else{
		if(l<=L){
			return tr[k].sr;
		}else{
			return ask(2*k+1,l,r,isl);
		}
	}
}

ll find(ll k,ll l,ll r){
	ll L=tr[k].l;
	ll R=tr[k].r;
	if(l<=L && R<=r){
		return tr[k].s;
	}
	ll mid=(L+R)/2;
	ll a=-1e18;
	ll b=-1e18;
	ll c=-1e17;
	ll d=-1e17;
	if(mid>=l){
		a=find(2*k,l,r);//左区间最值
		d=ask(2*k,l,r,0);
	}
	if(mid+1<=r){
		b=find(2*k+1,l,r);//右区间最值
		c=ask(2*k+1,l,r,1);
	}
	//c+d是中间链接部分最值
	return max(a,max(b,c+d));
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>inp[i];
	}
	build(1,1,n);
	while(m--){
		ll a,b,c;
		cin>>c>>a>>b;
		if(c==1){
			if(a>b){
				ll t=a;
				a=b;
				b=t;
			}
			ans.push_back(find(1,a,b));
		}else{
			change(1,a,b);
		}/*
		for(int i=1;i<=2*n;i++){
			cout<<tr[i].l<<" "<<tr[i].r<<" "<<tr[i].sum<<" "<<tr[i].s<<" "<<tr[i].sl<<" "<<tr[i].sr<<endl;
		}
		cout<<endl;*/
	}
	for(auto p=ans.begin();p!=ans.end();p++){
		cout<<*p<<endl;
	}
	return 0;
}