#include<cstdio>

 #include<cstring>

 #include<iostream>

 #define max(a,b) ((a)>(b)?(a):(b))

 using namespace std;

 inline int rd(){

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-; c=getchar();}

     while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

     return f*x;

 }

 const int maxn=+,maxm=+,inf=<<;

 int N,M,K,P,S,ans,flag;

 struct Tree{int lsum,rsum,l,r,mx,sum;}t[maxn<<],now;

 inline void Pushup(int x){

     int ls=x<<,rs=ls|;

     t[x].sum=t[ls].sum+t[rs].sum;

     t[x].lsum=max(t[ls].lsum,t[ls].sum+t[rs].lsum);

     t[x].rsum=max(t[rs].rsum,t[rs].sum+t[ls].rsum);

     t[x].mx=max(t[ls].mx,t[rs].mx);

     t[x].mx=max(t[x].mx,t[ls].rsum+t[rs].lsum);

     return;

 }

 inline void Build(int x,int l,int r){

     t[x].l=l;t[x].r=r;int mid=(l+r)>>;

     if(l==r){

         t[x].sum=t[x].lsum=t[x].rsum=t[x].mx=rd();

         return;

     }

     Build(x<<,l,mid);Build(x<<|,mid+,r);

     Pushup(x);

     return;

 }

 inline void Update(int x,int p,int s){

     int l=t[x].l,r=t[x].r,mid=(l+r)>>,ls=x<<,rs=ls|;

     if(l==r&&l==p){

         t[x].sum=t[x].lsum=t[x].rsum=t[x].mx=s;

         return;

     }

     if(p<=mid)Update(ls,p,s);else Update(rs,p,s);

     Pushup(x);

     return;

 }

 inline void Query(int x,int ql,int qr){

     int l=t[x].l,r=t[x].r,mid=(l+r)>>,ls=x<<,rs=ls|;

     if(ql<=l&&r<=qr){

         if(flag==-){

             flag=;

             now.lsum=t[x].lsum;now.rsum=t[x].rsum;

             now.mx=t[x].mx;now.sum=t[x].sum;

         }

         else{

             int sum,lsum,rsum,mx;

             sum=now.sum+t[x].sum;

             lsum=max(now.lsum,now.sum+t[x].lsum);

             rsum=max(t[x].rsum,now.rsum+t[x].sum);

             mx=max(now.mx,t[x].mx);

             mx=max(mx,now.rsum+t[x].lsum);

             now.sum=sum;now.lsum=lsum;now.rsum=rsum;now.mx=mx;

         }

         return;

     }

     if(ql<=mid)Query(ls,ql,qr);if(qr>mid)Query(rs,ql,qr);

     return;

 }

 int main(){

     N=rd();M=rd();

     Build(,,N);

     while(M--){

         K=rd();P=rd();S=rd();

         if(K==){

             if(P>S)swap(P,S);

             flag=-;

             Query(,P,S);

             ans=now.mx;

             printf("%d\n",ans);

         }

         else Update(,P,S);

     }

     return ;

 }