#include<bits/stdc++.h> using namespace std; #define ls pos<<1 #define rs pos<<1|1 const int N=2e5+10,M=50; int n,q,a[N]; struct Node{ int x[M+10],p; Node operator*(const Node&G)const{ Node res; res.p=min(M,p+G.p); int i=1,j=1; while(i+j-1<=res.p){ if(j>G.p||(x[i]>=G.x[j]&&i<=p)){res.x[i+j-1]=x[i];i++;} else{res.x[i+j-1]=G.x[j];j++;} } return res; } }t[N<<2]; int read(){ char c=getchar();bool op=0; if(c=='-')op=1; while(c>'9'||c<'0')c=getchar(); int d=0; while(c>='0'&&c<='9'){d=d*10+c-'0';c=getchar();} if(op)return -d; return d; } void pushup(int pos){t[pos]=t[ls]*t[rs];} void build(int pos,int l,int r){ // cout<<pos<<" "<<l<<" "<<r<<endl; if(l==r){t[pos].x[1]=a[l];t[pos].p=1;return;} int mid=(l+r)>>1; build(ls,l,mid);build(rs,mid+1,r); pushup(pos); } void modify(int pos,int l,int r,int x,int k){ if(l==r){t[pos].x[1]=k;return;} int mid=(l+r)>>1; if(x<=mid)modify(ls,l,mid,x,k); else modify(rs,mid+1,r,x,k); pushup(pos); } Node query(int pos,int l,int r,int ql,int qr){ if(l>=ql&&r<=qr){return t[pos];} int mid=(l+r)>>1;Node p,q; for(int i=1;i<=40;i++)p.x[i]=q.x[i]=0;p.p=q.p=0; if(ql<=mid)p=query(ls,l,mid,ql,qr); if(qr>mid)q=query(rs,mid+1,r,ql,qr); return p*q; } signed main(){ n=read();q=read(); for(int i=1;i<=n;i++)a[i]=read(); build(1,1,n); int op,x,y; while(q--){ op=read();x=read();y=read(); if(op==0){modify(1,1,n,x,y);} else{ Node ans=query(1,1,n,x,y); bool flag=0; for(int i=1;i<=ans.p-2;i++){ if(ans.x[i+1]+ans.x[i+2]>ans.x[i]){ int ANS=ans.x[i]+ans.x[i+1]+ans.x[i+2]; printf("%lld\n",ANS);flag=1;break; } } if(!flag)printf("0\n"); } } return 0; }