#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int lx[N<<2],rx[N<<2],rl[N<<2],s[N<<2],v[N],n,m;
void pushup(int rt){
    lx[rt]=max({lx[rt],lx[rt<<1],s[rt<<1]+lx[rt<<1|1]});
    rx[rt]=max({rx[rt],rx[rt<<1|1],s[rt<<1|1]+rx[rt<<1]});
    rl[rt]=max({lx[rt],rx[rt],rl[rt<<1],rl[rt<<1|1],rl[rt]});
    s[rt]=s[rt<<1]+s[rt<<1|1];
}
void build(int rt,int l,int r){
    if(l==r){
        lx[rt]=rx[rt]=rl[rt]=s[rt]=v[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
void xg(int rt,int l,int r,int fx,int fv){
    if(l==r && l==fx){
        lx[rt]=rx[rt]=rl[rt]=s[rt]=fv;
        return ;
    }
    int mid=(l+r)>>1;
    if(fx<=mid)  xg(rt<<1,l,mid,fx,fv);
    else   xg(rt<<1|1,mid+1,r,fx,fv);
    pushup(rt);
}
int xw(int rt,int l,int r,int fl,int fr){
    if(fl<=l && r<=fr)  return max({lx[rt],rl[rt],rx[rt]});
    int mid=(l+r)>>1,ans=0;
    if(fl<=mid)  ans=max(ans,xw(rt<<1,l,mid,fl,fr));
    if(mid<fr)   ans=max(ans,xw(rt<<1|1,mid+1,r,fl,fr));
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)   cin>>v[i];
    build(1,1,n);
    while(m--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1)   cout<<xw(1,1,n,l,r)<<endl;
        else    xg(1,1,n,l,r);
    }
    return 0;
}