#include <iostream>
#include <algorithm>
#include <cstring>
#define lson root<<1
#define rson root<<1|1
using namespace std;
const int N=5e5+15;
int n,m;
struct Node{
    int l,r,v;
    int mr,ml,mn,sum;
}tr[N<<2];
int a[N];
void Push_up(int root){
    tr[root].sum=tr[lson].sum+tr[rson].sum;
    tr[root].ml=max(tr[lson].ml,tr[lson].mn+tr[rson].ml);
    tr[root].mr=max(tr[rson].mr,tr[rson].mn+tr[lson].mr);
    tr[root].mn=max(max(tr[lson].mn,tr[rson].mn),tr[lson].mr+tr[rson].ml);
}
void build_tree(int l,int r,int root){
	tr[root].l=l; tr[root].r=r;
    if(l==r){
        tr[root].ml=tr[root].mr=tr[root].mn=tr[root].sum=a[r];
        return ;
    }
    int mid=l+r>>1;
    build_tree(l,mid,lson);
    build_tree(mid+1,r,rson);
    Push_up(root);
}
void Modify(int root,int p,int q){
    if(tr[root].l==tr[root].r){
        tr[root].sum=tr[root].ml=tr[root].mr=tr[root].mn=q;
        return ;
    }
    int mid=tr[root].l+tr[root].r>>1;
    if(p<=mid) Modify(lson,p,q);
    else Modify(rson,p,q);
    Push_up(root);
}
Node Query(int root,int l,int r){
    if(l<=tr[root].l && tr[root].r<=r)
        return tr[root];
    int mid=tr[root].l+tr[root].r>>1;
    if(r<=mid) return Query(lson,l,r);
    else{
        if(l>mid) return Query(rson,l,r);
        else{
            Node temp;
            Node x=Query(lson,l,r),y=Query(rson,l,r);
           //Node x,y;
            temp.ml=max(x.ml,x.mn+y.ml);
            temp.mr=max(y.mr,y.mn+x.mr);
            temp.mn=max(max(x.mn,y.mn),x.mr+y.ml);
            return temp;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build_tree(1,n,1);
    while(m--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            if(x>y) swap(x,y);
            cout<<Query(1,x,y).mn<<endl;
        }
        else Modify(1,x,y);
    }
    return 0;
}