#include<bits/stdc++.h>
#define int long long
#define ls k<<1
#define rs k<<1|1
#define qmi int mid=(tree[k].l+tree[k].r)>>1
using namespace std;
int n,m,a[500005];
struct node{
	int l,r,w,ms=LONG_LONG_MIN,ml=LONG_LONG_MIN,mr=LONG_LONG_MIN;
}tree[2000005];
void build(int l,int r,int k){
	tree[k].l=l;
	tree[k].r=r;
	if(l==r){
		tree[k].w=tree[k].ms=tree[k].ml=tree[k].mr=a[l];
		return ;
	}
	qmi;
	build(l,mid,ls);
	build(mid+1,r,rs);
	if(tree[ls].mr<0&&tree[rs].ml<0){
		tree[k].ms=max(tree[ls].mr,tree[rs].ml);
	}else{
		tree[k].ms=tree[ls].mr*(tree[ls].mr>0)+tree[rs].ml*(tree[rs].ml>0);
	}
	tree[k].w=tree[ls].w+tree[rs].w;
	tree[k].ml=max(tree[ls].ml,tree[ls].w+tree[rs].ml);
	tree[k].mr=max(tree[rs].mr,tree[rs].w+tree[ls].mr);
	tree[k].ms=max(tree[k].ms,max(tree[ls].ms,tree[rs].ms));
}
void update(int p,int x,int k){
	if(tree[k].l==tree[k].r){
		tree[k].w=tree[k].ml=tree[k].mr=tree[k].ms=x;
		return ;
	}
	qmi;
	if(p<=mid){
		update(p,x,ls);
	}else{
		update(p,x,rs);
	}
	if(tree[ls].mr<0&&tree[rs].ml<0){
		tree[k].ms=max(tree[ls].mr,tree[rs].ml);
	}else{
		tree[k].ms=tree[ls].mr*(tree[ls].mr>0)+tree[rs].ml*(tree[rs].ml>0);
	}
	tree[k].w=tree[ls].w+tree[rs].w;
	tree[k].ml=max(tree[ls].ml,tree[ls].w+tree[rs].ml);
	tree[k].mr=max(tree[rs].mr,tree[rs].w+tree[ls].mr);
	tree[k].ms=max(tree[k].ms,max(tree[ls].ms,tree[rs].ms));
}
int query(int l,int r,int k){
	if(tree[k].l>=l&&tree[k].r<=r){
		return tree[k].ms;
	}
	qmi;
	int ans=LONG_LONG_MIN;
	if(l<=mid){
		ans=max(ans,query(l,r,ls));
	}
	if(r>mid){
		ans=max(ans,query(l,r,rs));
	}
	return ans;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	while(m--){
		int k,l,r;
		cin>>k>>l>>r;
		if(k==1){
			if(l>r){
				swap(l,r);
			}
			cout<<query(l,r,1)<<"\n";
		}else{
			update(l,r,1);
		}
	}
    return 0;
}