#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

template <typename T>
void Read(T &x) {
    x=0;char c=getchar();
    T f=1;
    while(c<'0'||c>'9'){ if(c=='-'){f=-1;} c=getchar(); }
    x=c-'0';
    while((c=getchar())>='0' && c<='9'){ x=x*10+c-'0';}
    x*=f;
}
template <typename T, typename... Args>
void Read(T &x, Args &... args) {
    Read(x);
    Read(args...);
}

const int maxn=500005;
struct node{
	int s,l,r,t;
	int m;
	node(){}
	node(int v){
		s=v;l=r=t=v;
		m=v;
	}
};

node v[maxn*4+10],a[maxn];
void pushup(node&x,const node&l,const node&r){
    x.s=l.s+r.s;
    x.l=max(l.l,l.s+r.l);
    x.r=max(r.r,r.s+l.r);
    x.t=max(l.t,max(r.t,l.r+r.l));
    x.m=max(l.m,r.m);
}
void build(node a[],int l,int r,int id){
    if(l==r){
        v[id]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(a,l,mid,id<<1);
    build(a,mid+1,r,id<<1|1);
    pushup(v[id],v[id<<1],v[id<<1|1]);
}
node query(int x,int y,int id,int l,int r){
    if(x<=l && r<=y){
        return v[id];
    }
    int mid=(l+r)>>1;
    node res(-0x3f3f3f);
    if(x>mid){
        res=query(x,y,id<<1|1,mid+1,r);
    }else if(y<=mid){
        res=query(x,y,id<<1,l,mid);
    }else{
    	pushup(res,query(x,y,id<<1|1,mid+1,r),query(x,y,id<<1,l,mid));
    }
    return res;
}
void change(int p,node x,int id,int l,int r){
    if(l==r){
        v[id]=x;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid){
        change(p,x,id<<1,l,mid);
    }else{
        change(p,x,id<<1|1,mid+1,r);
    }
    pushup(v[id],v[id<<1],v[id<<1|1]);
}

int main(){
	
	int n,m,k,q,p;
	Read(n,m);
	for(int i=1;i<=n;i++){
		Read(a[i].s);
		a[i].l=a[i].r=a[i].t=a[i].s;
		a[i].m=a[i].s;
	}
	build(a,1,n,1);
	for(int i=1;i<=m;i++){
		Read(k,q,p);
		if(k==1){
			if(q>p){
				swap(q,p);
			}
			if(query(q,p,1,1,n).m<0){
				printf("%d\n",query(q,p,1,1,n).m);
			}else{
				printf("%d\n",query(q,p,1,1,n).t);
			}
			
		}else if(k==2){
			change(q,node(p),1,1,n);
		}
	}
	
	return 0;
}