#include<bits/stdc++.h>
#define lc(p) t[p*2]
#define rc(p) t[p*2+1]
using namespace std;
typedef long long ll;
const int maxn=1000010;
int a[maxn+2];
struct node{
    int l,r;
    long long val,lazy;
    ll sum,dat,lm,rm;
}t[4*maxn+2];
void merge(int p)
{
	//t[p].val=t[p*2].val+t[p*2+1].val;
    t[p].sum=lc(p).sum+rc(p).sum;
    t[p].lm=max(lc(p).lm,lc(p).sum+rc(p).lm);
    t[p].rm=max(rc(p).rm,rc(p).sum+lc(p).rm);
    t[p].dat=max(max(lc(p).dat,rc(p).dat),lc(p).rm+rc(p).lm);
}
void bulid(int p,int l,int r){
    t[p].l=l;t[p].r=r;
    if(l==r){
        t[p].sum=t[p].dat=t[p].lm=t[p].rm=a[l];
        return;
    }
    int mid=l+r>>1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    merge(p);
} 


void change(int p,int x,int y)
{
	if(t[p].l==t[p].r) 
	{
		t[p].val=t[p].sum=t[p].dat=t[p].lm=t[p].rm=y;
		return;
	}
	int mid=t[p].l+t[p].r>>1;
	if(x<mid) change(p*2,x,y);
	else change(p*2+1,x,y);
	merge(p);
}

node query(int p,int x,int y){
    if(x<=t[p].l && y>=t[p].r) return t[p];
    int mid=t[p].l+t[p].r>>1;
    //long long ans=0;
    //if(x<=mid) ans+=query(p*2,x,y);
    //if(y>mid) ans+=query(p*2+1,x,y);
    if(y<=mid) return query(p*2,x,y);
    if(x>mid) return query(p*2+1,x,y);
    else
    {
    	node ans,lt=query(p*2,x,y),rt=query(p*2+1,x,y);
    	ans.dat=ans.lm=ans.rm=-0x7fffff;
    	ans.sum=0;
    	ans.lm=max(lt.lm,lt.sum+rt.lm);
    	ans.rm=max(rt.rm,rt.sum+lt.rm);
    	ans.dat=max(max(lt.dat,rt.dat),lt.dat+rt.dat);
    	return ans;
	}
    
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    bulid(1,1,n);
    while(m--)
    {
        int k,a,b;
        cin>>k>>a>>b;
        if(k==1)
        {
        	if(a>b) swap(a,b);
        	cout<<query(1,a,b).dat<<endl;
		}
		else 
		{
			change(1,a,b);
		}
    }
    return 0;
}