#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;
int n,m,a,x,y;
struct Segment_tree{
#define ls o<<1
#define rs o<<1|1
	struct dog{int x,s,l,r;}t[N<<2];
	void init(){memset(t,-0x3f3f3f3f,sizeof(t));}
	void pushup(int o){
		t[o].x=max(max(t[ls].x,t[rs].x),t[ls].r+t[rs].l),t[o].s=t[ls].s+t[rs].s,
		t[o].l=max(t[ls].l,t[ls].s+t[rs].l),t[o].r=max(t[ls].r,t[rs].s+t[ls].r);
	}
	void modify(int x,int y,int l=1,int r=n,int o=1){
		if(l==r){t[o]={y,y,y,y};return;}
		int mid=l+r>>1;
		if(x<=mid)modify(x,y,l,mid,ls);
		else modify(x,y,mid+1,r,rs);
		pushup(o);
	}
	dog query(int ql,int qr,int l=1,int r=n,int o=1){
		if(ql<=l&&r<=qr)return t[o];
		int mid=l+r>>1;
		dog t0,t1,res;int c;
		if(ql>mid&&qr>mid)return query(ql,qr,mid+1,r,rs);
		if(ql<=mid&&qr<=mid)return query(ql,qr,l,mid,ls);
		t0=query(ql,qr,l,mid,ls);
		t1=query(ql,qr,mid+1,r,rs);
		res.s=t0.s+t1.s;
		res.l=max(t0.l,t0.s+t1.l);
		res.r=max(t1.r,t1.s+t0.r);
		res.x=max(max(t0.x,t1.x),t0.r+t1.l);
		return res;
	}
}T;
main(){
	T.init();
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%lld",&x),
		T.modify(i,x);
	for(int i=1;i<=m;++i){
		scanf("%lld%lld%lld",&a,&x,&y);
		if(a==1){
			if(x>y)swap(x,y);
			printf("%lld\n",T.query(x,y).x);
		}
		else T.modify(x,y);
	}
}