#include<bits/stdc++.h> using namespace std; #define int long long int n,q,a[200005]; struct node{ int mx[60],tot; node(){memset(mx,0,sizeof(mx));tot=0;} void prt(){ for(int i=1;i<=tot;i++)cout<<mx[i]<<" "; cout<<endl; } }; node operator+(node x,node y){ // cout<<"+\n"; // x.prt(); // y.prt(); int tp1=1,tp2=1; node res; res.tot=0; while(1){ // cout<<res.tot<<" "<<tp1<<" "<<x.tot<<" "<<tp2<<" "<<y.tot<<endl; if(res.tot==45||(tp1>x.tot&&tp2>y.tot))break; 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++]; } } // res.prt(); 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[l]; 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; 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; } void prt(int l,int r,int p){ cout<<l<<" "<<r<<endl; t[p].prt(); if(l==r){ return; } prt(l,mid,ls); prt(mid+1,r,rs); } int calc(int l,int r){ node x=qu(1,n,l,r,1); // x.prt(); 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]); bd(1,n,1); // prt(1,n,1); 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(){ //freopen("triangle.in","r",stdin); //freopen("triangle.out","w",stdout); slv(); return 0; }