#include<bits/stdc++.h>
using namespace std;
long long a[2000005],n,m;
struct node{
	long long l,r,Max,sum;
}seg[2000005];
inline void pushup(long long k){
	seg[k].l=max(seg[k<<1].l,seg[k<<1].sum+seg[k<<1|1].l);
	seg[k].r=max(seg[k<<1|1].r,seg[k<<1|1].sum+seg[k<<1].r);
	seg[k].sum=seg[k<<1].sum+seg[k<<1|1].sum;
	seg[k].Max=max(max(seg[k<<1|1].Max,seg[k<<1].Max),seg[k<<1].r+seg[k<<1|1].l);
	return;
}  
inline void build(long long l,long long r,long long k){
	if(l==r){
		seg[k].l=a[l];
		seg[k].r=a[l];
		seg[k].Max=a[l];
		seg[k].sum=a[l];
		return;
	}
	long long mid=l+r>>1;
	build(l,mid,k<<1);
	build(mid+1,r,k<<1|1);
	pushup(k);
	return;
}	
inline void update(long long p,long long num,long long l,long long r,long long k){
	if(l==p&&r==p){
		//a[l]=num;
		seg[k].l=num;
		seg[k].r=num;
		seg[k].Max=num;
		seg[k].sum=num;
		return;
	}
	long long mid=l+r>>1;
	if(p<=mid) update(p,num,l,mid,k<<1);
	if(p>mid) update(p,num,mid+1,r,k<<1|1);
	pushup(k);
}
inline node query(long long L,long long R,long long l,long long r,long long k){
	if(L<=l&&r<=R){
		return seg[k];
	}
	long long mid=l+r>>1,ans=0;
	if(L<=mid) return query(L,R,l,mid,k<<1);
	else if(R>mid) return query(L,R,mid+1,r,k<<1|1);
	if(L<=mid&&R>mid){
		node ret,tmpl=query(L,R,l,mid,k<<1),tmpr=query(L,R,mid+1,r,k<<1|1);	
		ret.l=max(tmpl.l,tmpl.sum+tmpr.l);
		ret.r=max(tmpr.r,tmpr.sum+tmpl.r);
		ret.sum=tmpl.sum+tmpr.sum;
		ret.Max=max(max(tmpr.Max,tmpl.Max),tmpl.r+tmpr.l);
    	return ret;
	}
}
int main(){
	scanf("%lld %lld",&n,&m);
	for(long long i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,n,1);
	for(long long i=1;i<=m;i++){
		long long l=0,r=0,op=0,p=0,s=0;
		scanf("%lld",&op);
		if(op==1){
			scanf("%lld %lld",&l,&r);
			if(l>r) swap(l,r);
			printf("%lld\n",query(l,r,1,n,1).Max);
		}
		if(op==2){
			scanf("%lld %lld",&p,&s);
			update(p,s,1,n,1);
		}	
	}
	return 0;
}