#include<cstdio>
int read(){
  int x; 
  scanf("%d",&x);
  return x;
}
#define max(a,b) (a>b?a:b)
#define N 500001
struct sgt{
#define sum(h)tr[h].sum
#define le(h)tr[h].le
#define ri(h)tr[h].ri
#define mx(h)tr[h].mx
  long sum,le,ri,mx;
}tr[N<<2];
sgt operator+(sgt,sgt);
#define mid (l+r>>1)
#define Lson h<<1,l,mid
#define Rson h<<1|1,mid+1,r
#define ls h<<1
#define rs h<<1|1
#define TREE int h,int l,int r
#define ALL sum(h)=le(h)=ri(h)=mx(h)
void push_up(int h){
  tr[h]=tr[ls]+tr[rs];
  /*
  sum(h)=sum(ls)+sum(rs);
  le(h)=max(le(ls),sum(ls)+le(rs));
  ri(h)=max(ri(rs),sum(rs)+ri(ls));
  mx(h)=max(max(mx(ls),mx(rs)),ri(ls)+le(rs));//max sum in this [l,r]
  */
}
void build(TREE){
  if(l==r)ALL=read();
  else{
    build(Lson),build(Rson);
    push_up(h);
  }
}
void modify(TREE,int p,int x){
  if(l==r)ALL=x;
  else {
    //push_down(TREE);  (no need)
    if(p<=mid)modify(Lson,p,x);
    else modify(Rson,p,x);
    push_up(h);
  }
}
sgt operator+(sgt aa,sgt bb){
  sgt ans;
  ans.sum=aa.sum+bb.sum;
  ans.le=max(aa.le,aa.sum+bb.le);
  ans.ri=max(bb.ri,bb.sum+aa.ri);
  ans.mx=(aa.ri>0)*aa.ri+(bb.le>0)*bb.le+(aa.ri<0&&bb.le<0)*max(aa.ri,bb.le); //all<0 choose one
  ans.mx=max(max(aa.mx,bb.mx),ans.mx);
  return ans;
}
sgt operator+=(sgt&aa,sgt bb){
  return aa=aa+bb;
}
sgt query(TREE,int x,int y){
  if(x<=l&&r<=y)return tr[h];
  sgt ans={0l,0l,0l,0l};
  if(x<=mid)ans=query(Lson,x,y);
  if(y>mid)ans+=query(Rson,x,y);
  return ans;
}
main(){
  int n,m;
  scanf("%d%d",&n,&m);
  build(1,1,n);
  for(int opt,x,y;m--;){
    scanf("%d%d%d",&opt,&x,&y);
    if(opt==1){
      if(x>y)x^=y^=x^=y;
      printf("%lld\n",query(1,1,n,x,y).mx);
    }
    else modify(1,1,n,x,y);
  }
}