#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define pb push_back #define lson (pos<<1) #define rson (pos<<1|1) int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=200010,N=60; int n,q,a[MAXN],p[MAXN],cnt; struct node{ int p[N],x; node operator*(const node&G)const{ node res; res.x=min(50ll,x+G.x); for(int i=1,j=1,o=1;o<=res.x;o++){ if(i>x||(j<=G.x&&G.p[j]>p[i]))res.p[o]=G.p[j],j++; else res.p[o]=p[i],i++; } return res; } }; struct segtree{ node t[MAXN<<2]; void pushup(int pos){ t[pos]=t[lson]*t[rson]; } void build(int pos,int l,int r){ if(l==r){ t[pos].x=1; t[pos].p[1]=a[l]; return; } int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); pushup(pos); } void update(int pos,int l,int r,int x,int y){ if(l==r){ t[pos].x=1; t[pos].p[1]=y; return; } int mid=(l+r)>>1; if(x<=mid)update(lson,l,mid,x,y); else update(rson,mid+1,r,x,y); pushup(pos); } node query(int pos,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r)return t[pos]; int mid=(l+r)>>1; if(qr<=mid)return query(lson,l,mid,ql,qr); if(ql>mid)return query(rson,mid+1,r,ql,qr); return query(lson,l,mid,ql,qr)*query(rson,mid+1,r,ql,qr); } }T; void slv(){ n=read(),q=read(); for(int i=1;i<=n;i++)a[i]=read(); T.build(1,1,n); while(q--){ int op=read(),l=read(),r=read(); if(op==0){ T.update(1,1,n,l,r); } else{ node tmp=T.query(1,1,n,l,r); int ans=0; for(int i=1;i<=tmp.x-2;i++){ if(tmp.p[i]<tmp.p[i+1]+tmp.p[i+2]) ans=max(ans,tmp.p[i]+tmp.p[i+1]+tmp.p[i+2]); } printf("%lld\n",ans); } } } signed main(){ slv(); return 0; }