rt

#include<bits/stdc++.h>
#define lowbit(x) x&-x
using namespace std;
int const maxn=5e5+10,maxm=1e5+10;
int n,m,a[maxn];
struct node{
	int l,r,sum,ma,lmax,rmax,lazy;
}tree[maxn<<2];
void push_up(int i){
	tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
	tree[i].lmax=tree[i].rmax=-2e9;
	tree[i].ma=0;
	if(tree[i<<1].rmax<0&&tree[i<<1|1].lmax<0){
		tree[i].ma=max(tree[i<<1].rmax,tree[i<<1|1].lmax);
	}else{
		if(tree[i<<1].rmax>0) tree[i].ma+=tree[i<<1].rmax;
		if(tree[i<<1|1].lmax>0) tree[i].ma+=tree[i<<1|1].lmax;
	}
	tree[i].ma=max(tree[i].ma,max(tree[i<<1].ma,tree[i<<1|1].ma));
	tree[i].lmax=max(tree[i].lmax,max(tree[i<<1].lmax,tree[i<<1].sum+tree[i<<1|1].lmax));
	tree[i].rmax=max(tree[i].rmax,max(tree[i<<1|1].rmax,tree[i<<1].rmax+tree[i<<1|1].sum));
}
void push_down(int i){
	if(tree[i].lazy){
		tree[i<<1].lazy+=tree[i].lazy;
		tree[i<<1|1].lazy+=tree[i].lazy;
		tree[i<<1].sum+=(tree[i<<1].r-tree[i<<1].l+1)*tree[i].lazy;
		tree[i<<1|1].sum+=(tree[i<<1|1].r-tree[i<<1|1].l+1)*tree[i].lazy;
	}
}
void build(int l,int r,int i){
	tree[i].l=l,tree[i].r=r;
	if(l==r){
		tree[i].sum=tree[i].ma=tree[i].lmax=tree[i].rmax=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(l,mid,i<<1);
	build(mid+1,r,i<<1|1);
	push_up(i); 
}
void modify(int l,int r,int i,int k){
	if(tree[i].l>=l&&tree[i].r<=r){
		tree[i].sum=tree[i].ma=tree[i].lmax=tree[i].rmax=k;
		return ;
	}
	push_down(i);
	if(l<=tree[i<<1].r) modify(l,r,i<<1,k);
	if(r>=tree[i<<1|1].l) modify(l,r,i<<1|1,k);
	push_up(i);
}
node query(int l,int r,int i){
	if(tree[i].l>=l&&tree[i].r<=r){
		return tree[i]; 
	}
	node ansl={0,0,-1e9,-1e9,-1e9,-1e9,0},ansr={0,0,-1e9,-1e9,-1e9,-1e9,0},ans;
	if(l<=tree[i<<1].r) ansl=query(l,r,i<<1);
	if(r>=tree[i<<1|1].l) ansr=query(l,r,i<<1|1);
	ans.ma=max(ansl.rmax+ansr.lmax,max(ansl.ma,ansr.ma));
	ans.sum=ansl.sum+ansr.sum;
	ans.lmax=max(ansl.lmax,ansl.sum+ansr.lmax);
	ans.rmax=max(ansr.rmax,ansr.sum+ansl.rmax);
	return ans;
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int k;
		cin>>k;
		if(k==1){
			int l,r;
			cin>>l>>r;
			node t=query(l,r,1);
			cout<<max(t.ma,max(t.lmax,t.rmax))<<"\n";
		}else{
			int p,s;
			cin>>p>>s;
			modify(p,p,1,s);
		}
	}
	return 0;
}