#include<bits/stdc++.h> using namespace std; #define N 200005 struct node { int l,r,v[50],siz; }tr[N*2]; int n,q; int a[N]; bool leaf(int id){ return tr[id].l==tr[id].r; } void maintain(int id){ tr[id].siz=0; int sz1=tr[id*2].siz,sz2=tr[id*2+1].siz; int p1=1,p2=1; while (p1<=sz1 && p2<=sz2 && tr[id].siz<40) { tr[id].siz++; if(tr[id*2].v[p1]>tr[id*2+1].v[p2]){ tr[id].v[tr[id].siz]=tr[id*2].v[p1]; p1++; }else{ tr[id].v[tr[id].siz]=tr[id*2+1].v[p2]; p2++; } } while(p1<=sz1 && tr[id].siz<40){ tr[id].v[++tr[id].siz]=tr[id*2].v[p1]; p1++; } while(p2<=sz2 && tr[id].siz<40){ tr[id].v[++tr[id].siz]=tr[id*2+1].v[p2]; p2++; } } void build(int l,int r,int id){ tr[id].l=l,tr[id].r=r; if(leaf(id)){ tr[id].siz=1; tr[id].v[1]=a[l]; return; } tr[id].siz=0; int mid=(l+r)/2; build(l,mid,id*2); build(mid+1,r,id*2+1); maintain(id); } void update(int p,int v,int id){ if(leaf(id)){ tr[id].v[1]=v; return; } int mid=(tr[id].l+tr[id].r)/2; if(p<=mid) update(p,v,id*2); else update(p,v,id*2+1); maintain(id); } int tmp[N*2][50],sz[N*2],tot; int tmpmt(int id1,int id2){ tot++; int sz1=sz[id1],sz2=sz[id2],p1=1,p2=1; while (p1<=sz1 && p2<=sz2 && sz[tot]<40) { sz[tot]++; if(tmp[id1][p1]>tmp[id2][p2]){ tmp[tot][sz[tot]]=tmp[id1][p1++]; }else{ tmp[tot][sz[tot]]=tmp[id2][p2++]; } } while (p1<=sz1 && sz[tot]<40){ sz[tot]++; tmp[tot][sz[tot]]=tmp[id1][p1++]; } while (p2<=sz2 && sz[tot]<40){ sz[tot]++; tmp[tot][sz[tot]]=tmp[id2][p2++]; } return tot; } int ask(int l,int r,int id){ if(leaf(id)){ tmp[++tot][1]=tr[id].v[1]; sz[tot]=1; return tot; } int mid=(tr[id].l+tr[id].r)/2; int id1=0,id2=0; if(l<=mid) id1=ask(l,r,id*2); if(r>mid) if(id1) id2=ask(l,r,id*2+1); else id1=ask(l,r,id*2+1); if(id2) return tmpmt(id1,id2); else return id1; } int main(){ ios::sync_with_stdio(false); cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i]; build(1,n,1); for(int i=1;i<=q;i++){ bool op; int x,y; cin>>op>>x>>y; if(op){ if(y<x+2){ cout<<0<<endl; continue; } bool ok=0; int id=ask(x,y,1); int a1=tmp[id][1],a2=tmp[id][2],a3; for(int i=3;i<=sz[id];i++){ a3=tmp[id][i]; if(a1<a2+a3){ cout<<a1+a2+a3<<endl; ok=1; break; } a1=a2; a2=a3; } if(!ok){ cout<<0<<endl; continue; } }else{ update(x,y,1); } } return 0; }