#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
int n,m,a[500005]; 
struct node{
	int s1,s2,s3,s4;
}t[2000005];
void push_up(int x){
	t[x].s1=t[x*2].s1+t[x*2+1].s1;
	t[x].s2=max(t[x*2].s2,t[x*2].s1+t[x*2+1].s2);
	t[x].s3=max(t[x*2+1].s3,t[x*2+1].s1+t[x*2].s3);
	t[x].s4=max(max(t[x*2].s4,t[x*2+1].s4),t[x*2].s2+t[x*2+1].s3);
} 
void build(int l,int r,int x){
	if(l==r){
		t[x].s1=t[x].s2=t[x].s3=t[x].s4=a[l];
		return;
	}
	build(l,mid,x*2);
	build(mid+1,r,x*2+1);
	push_up(x);
}
node ask(int L,int R,int l,int r,int x){
	if(l>=L&&r<=R)return t[x];
	if(R<=mid)return ask(L,R,l,mid,x*2);
	if(L>mid)return ask(L,R,mid+1,r,x*2+1);
	node ans,a1=ask(L,R,l,mid,x*2),b1=ask(L,R,mid+1,r,x*2+1);
	ans.s1=a1.s1+b1.s1;
	ans.s2=max(a1.s2,a1.s1+b1.s2);
	ans.s3=max(b1.s3,b1.s1+a1.s3);
	ans.s4=max(max(a1.s4,b1.s4),a1.s2+b1.s3);
	return ans;
}
void add(int d,int e,int l,int r,int x){
	if(l==r){
		t[x].s1=t[x].s2=t[x].s3=t[x].s4=e;
		return;
	}
	if(d<=mid)add(d,e,l,mid,x*2);
	else add(d,e,mid+1,r,x*2+1); 
	push_up(x);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	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);
			printf("%d\n",ask(x,y,1,n,1).s4);
		}else{
			add(x,y,1,n,1);
		}
	}
	return 0;
}

AC第一个点