#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
int a[N<<2],pre[N<<2],suf[N<<2],s[N<<2];
int b[N],cnt;
void pushup(int u){
	a[u]=a[u<<1]+a[u<<1|1];
	pre[u]=max(pre[u<<1],a[u<<1]+pre[u<<1|1]);
	suf[u]=max(suf[u<<1|1],a[u<<1|1]+suf[u<<1]);
	s[u]=max(max(s[u<<1],s[u<<1|1]),suf[u<<1]+pre[u<<1|1]);
}
void build(int l,int r,int u){
	if(l==r){
		scanf("%d",a+u);
		b[++cnt]=u;
		pre[u]=suf[u]=s[u]=a[u];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,u<<1);
	build(mid+1,r,u<<1|1);
	pushup(u);
}
int h=0;
void update(int p,int l,int r,int u,int k){
//	cout<<'@'<<b[p]<<' '<<u<<'\n';
//	if(++h==50)exit(0);
	if(b[p]==u){
		a[u]=k;
		pre[u]=suf[u]=s[u]=a[u];
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid)update(p,l,mid,u<<1,k);
	if(p>mid)update(p,mid+1,r,u<<1|1,k);
	pushup(u);
//	cout<<'#'<<u<<' '<<s[u]<<' '<<suf[u<<1]<<' '<<pre[u<<1|1]<<'\n';
}
int asksum(int L,int R,int l,int r,int u){
	if(L<=l&&r<=R){
		return a[u];
	}
	int mid=(l+r)>>1;
	int sum=0;
	if(L<=mid)sum+=asksum(L,R,l,mid,u<<1);
	if(R>mid)sum+=asksum(L,R,mid+1,r,u<<1|1);
	return sum;	
}
int fsuf(int L,int R,int l,int r,int u){
	if(L<=l&&r<=R){
		return suf[u];
	}
	int mid=(l+r)>>1,M=(L+R)>>1;
	int p1=INT_MIN,p2=INT_MIN;
	if(R<=mid)return fsuf(L,R,l,mid,u<<1);
	p1=fsuf(L,R,mid,r,u<<1|1);
	if(L<=mid)p2=asksum(L,R,mid,r,u<<1|1)+fsuf(L,R,l,mid,u<<1);
	return max(p1,p2);
}
int fpre(int L,int R,int l,int r,int u){
	if(L<=l&&r<=R)return pre[u];
	int mid=(l+r)>>1;
	int p1=INT_MIN,p2=INT_MIN;
	if(L>mid)return fpre(L,R,mid+1,r,u<<1|1);
	p1=fpre(L,R,l,mid,u<<1);
	if(R>mid)p2=asksum(L,R,l,mid,u<<1)+fpre(L,R,mid+1,r,u<<1|1);
	return max(p1,p2);
}
int query(int L,int R,int l,int r,int u){
	if(L<=l&&r<=R){
		return s[u];
	}
	int mid=(l+r)>>1;
	int ml=INT_MIN,mr=INT_MIN,mm=INT_MIN;
	if(L<=mid)ml=query(L,R,l,mid,u<<1);
	if(R>mid)mr=query(L,R,mid+1,r,u<<1|1);
	if(L<=mid&&R>mid) mm=fsuf(L,R,l,mid,u<<1)+fpre(L,R,mid+1,r,u<<1|1);
//	cout<<u<<' '<<ml<<' '<<mr<<' '<<mm<<'\n';
	return max(max(ml,mr),mm);
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,n,1);
	while(m--){
		int k,x,y;
		scanf("%d%d%d",&k,&x,&y);
		if(k==1){
			if(x>y)swap(x,y);
			int res=0;
			res=query(x,y,1,n,1);
			printf("%d\n",res);
		}else{
			update(x,1,n,1,y);
		}
	}
	return 0;
}