#include<bits/stdc++.h> using namespace std; #define int long long int n,q,a[200005]; struct node{ int mx[60],tot; }; node operator+(node x,node y){ int tp1=1,tp2=1; node res; while(1){ if(res.tot==50||(tp1>=x.tot&&tp2>=y.tot))return res; if(tp2>=y.tot||x.mx[tp1]>y.mx[tp2]){ res.mx[++res.tot]=x.mx[tp1++]; } else{ res.mx[++res.tot]=y.mx[tp2++]; } } return res; } node t[800005]; #define ls (p<<1) #define rs (p<<1|1) #define mid (l+r>>1) void pu(int p){ t[p]=t[ls]+t[rs]; } void bd(int l,int r,int p){ if(l==r){ t[p].mx[t[p].tot=1]=a[p]; return; } bd(l,mid,ls); bd(mid+1,r,rs); pu(p); } void upd(int l,int r,int id,int x,int p){ if(l==r){ t[p].mx[t[p].tot=1]=x; return; } if(mid>=id)upd(l,mid,id,x,ls); else upd(mid+1,r,id,x,rs); pu(p); } node qu(int l,int r,int ml,int mr,int p){ if(ml<=l&&r<=mr)return t[p]; node res={{},0}; if(mid>=ml) res=res+qu(l,mid,ml,mr,ls); if(mid<mr)res=res+qu(mid+1,r,ml,mr,rs); return res; } int calc(int l,int r){ node x=qu(1,n,l,r,1); for(int i=1;i+2<=x.tot;i++){ if(x.mx[i+2]+x.mx[i+1]>x.mx[i])return x.mx[i+2]+x.mx[i+1]+x.mx[i]; } return 0; } void read(int &x){ x=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))x=x*10+c-'0',c=getchar(); return; } void slv(){ read(n),read(q); for(int i=1;i<=n;i++)read(a[i]); while(q--){ int op,x,y; read(op),read(x),read(y); if(op==0)upd(1,n,x,y,1); else printf("%lld\n",calc(x,y)); } } signed main(){ slv(); return 0; }