#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=5e5+10;
int n,m,chu[N];
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
struct node{
	int lmax,rmax,max,sum;
}tree[N*4];
void push_up(int p){
     	tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum;
	    tree[p].max=(tree[ls(p)].rmax+tree[rs(p)].lmax,max(tree[ls(p)].max,tree[rs(p)].max));
		tree[p].lmax=max(tree[ls(p)].sum+tree[rs(p)].lmax,tree[ls(p)].lmax);
		tree[p].rmax=max(tree[rs(p)].sum+tree[ls(p)].rmax,tree[rs(p)].rmax);
}
void build(int p,int l,int r){
	if(l==r){
		tree[p].lmax=tree[p].max=tree[p].rmax=tree[p].sum=chu[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
node query(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return tree[p];
	}
		int mid=(l+r)>>1;
		if(R<=mid)return query(ls(p),l,mid,L,R);
		else if(L>mid)return query(rs(p),mid+1,r,L,R);
		else{
			node t,x=query(ls(p),l,mid,L,R),y=query(rs(p),mid+1,r,L,R);
			t.lmax=max(x.lmax,x.sum+y.lmax);
            t.rmax=max(y.rmax,x.rmax+y.sum);
            t.max=max(max(x.max,y.max),x.rmax+y.lmax);
            return t;
		}
}
void change(int p,int l,int r,int x,int s){
	if(l==r){
		tree[p].sum=tree[p].max=tree[p].lmax=tree[p].rmax=s;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)change(ls(p),l,mid,x,s);
	else change(rs(p),mid+1,r,x,s);
	push_up(p);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>chu[i];
	}
	build(1,1,n);
	while(m--){
		int k;
		cin>>k;
		if(k==1){
			int a,b;
			cin>>a>>b;
			if(a>b)swap(a,b);
			node x=query(1,1,n,a,b);
			cout<<x.max<<endl;
		}else{
			int p,s;
			cin>>p>>s;
			change(1,1,n,p,s);
		}
	}
	return 0;
}