#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define lson s,mid,ls
#define rson mid+1,t,rs
using namespace std;
const int Maxn=1e6+10;
const int mod=1e9+7;
typedef long long ll;
namespace io{
	const int _SIZE=(1<<21)+1;
	char ibuf[_SIZE],*iS,*iT,c,stk[40];int tot;
#define gc()(iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,_SIZE,stdin),(iS==iT ?EOF:*iS++)):*iS++)
	template<class I>
	inline void read(I &_x){
		I fl=1;
		for(c=gc();c<'0'||c>'9';c=gc()) if(c=='-') fl=-1;
		for(_x=0;c>='0'&&c<='9';c=gc()) _x=_x*10+(c&15);
		_x*=fl;
	}
	template<class I>
	inline void prt(I _x,char ch='\0'){
		tot=0;
		if(_x<0) putchar('-'),_x*=-1;
		do{
			stk[tot++]=_x%10|48;_x/=10;
		}while(_x);
		do{
			putchar(stk[--tot]);
		}while(tot);
		if(ch)putchar(ch);
	}
}
using io::read;
using io::prt;
inline int rd(){
	static int x;int f=1;
	static char c;
	while((c=getchar())<'0'||c>'9') if(c=='-') f=-1;
	x=(c&15);
	while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15);
	return x*f;
}
int n,m;
int a[Maxn];
struct tree{
	int l,r,maxx,sum;
}st[Maxn<<2];
tree merge(tree a,tree b){
	tree c;
	c.sum=a.sum+b.sum;
	c.l=max(a.l,a.sum+b.l);
	c.r=max(b.r,b.sum+a.r);
	c.maxx=max(max(a.maxx,b.maxx),a.r+b.l);
	return c;
}
void build(int s,int t,int p){
	if(s==t){
		st[p].sum=a[s];
		st[p].l=a[s];
		st[p].r=a[s];
		st[p].maxx=a[s];
		return;
	}
	int mid=s+t>>1;
	build(lson),build(rson);
	st[p]=merge(st[ls],st[rs]);
}
tree ask(int l,int r,int s,int t,int p){
	if(l<=s&&t<=r) return st[p];
	int mid=s+t>>1;
	if(r<=mid) return ask(l,r,lson);
	if(mid+1<=l) return ask(l,r,rson);
	tree a,b,c;
	a=ask(l,r,lson),b=ask(l,r,rson);
	c=merge(a,b);
	return c;
}
void change(int x,int k,int s,int t,int p){
	if(s==t){
		st[p].l=k;
		st[p].sum=k;
		st[p].r=k;
		st[p].maxx=k;
		return;
	}
	int mid=s+t>>1;
	if(x<=mid) return change(x,k,lson);
	if(mid+1<=x) return change(x,k,rson);
	st[p]=merge(st[ls],st[rs]);
}
int main(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	build(1,n,1);
	while(m--){
		int k,x,y;
		read(k),read(x),read(y);
		if(k==2) change(x,y,1,n,1);
		else{
			if(x>y) swap(x,y);
			tree ans=ask(x,y,1,n,1);
			prt(ans.maxx,'\n');
		}
	}
	return 0;
}

rt