#include<bits/stdc++.h> #define ls(x) (x<<1) #define rs(x) (x<<1|1) using namespace std; const int N=200010; struct node{ int maxn[50]; int siz; }t[4*N]; node k; int n,q,op; int a[N]; void push_up(int u,int l,int r){ int l1=0,l2=0; int cnt=0; while(cnt<50){ //cout<<"@"<<l1<<" "<<l2<<" "<<t[ls(u)].siz<<" "<<t[rs(u)].siz<<endl; while(l1<t[ls(u)].siz&&cnt<50&&(t[ls(u)].maxn[l1]>=t[rs(u)].maxn[l2]||l2>=t[rs(u)].siz)){ t[u].maxn[cnt++]=t[ls(u)].maxn[l1]; l1++; } while(l2<t[rs(u)].siz&&cnt<50&&(t[rs(u)].maxn[l2]>t[ls(u)].maxn[l1]||l1>=t[ls(u)].siz)){ t[u].maxn[cnt++]=t[rs(u)].maxn[l2]; l2++; } if(l1>=t[ls(u)].siz&&l2>=t[rs(u)].siz) break; } t[u].siz=cnt; return; } void build(int u,int l,int r){ //cout<<u<<" "; //return; if(l==r){ t[u].maxn[0]=a[l]; t[u].siz=1; return; } int mid=(l+r)>>1; build(ls(u),l,mid); build(rs(u),mid+1,r); push_up(u,l,r); return; } void re(int u,int l,int r,int x,int v){ //cout<<u<<" "; if(l==r){ t[u].maxn[0]=v; a[l]=v; return; } int mid=(l+r)>>1; if(x<=mid) re(ls(u),l,mid,x,v); else re(rs(u),mid+1,r,x,v); push_up(u,l,r); } int merge(int u){ int l1=0,l2=0; int cnt=0; node z; while(cnt<50){ while(l1<t[u].siz&&cnt<50&&(t[u].maxn[l1]>=k.maxn[l2]||l2>=k.siz)){ z.maxn[cnt++]=t[u].maxn[l1]; l1++; } while(l2<k.siz&&cnt<50&&(k.maxn[l2]>t[u].maxn[l1]||l1>=t[u].siz)){ z.maxn[cnt++]=k.maxn[l2]; l2++; } if(l1>=t[u].siz&&l2>=k.siz) break; } k.siz=cnt; for(int i=0;i<cnt;i++) k.maxn[i]=z.maxn[i]; } void find(int u,int l,int r,int x,int y){ if(x<=l&&r<=y){ merge(u); return; } int mid=(l+r)>>1; if(x<=mid) find(ls(u),l,mid,x,y); if(y>mid) find(rs(u),mid+1,r,x,y); return; } int main(){ cin>>n>>q; //cout<<"!"<<" "<<n<<" "<<q<<endl; for(int i=1;i<=n;i++){ cin>>a[i]; //cout<<i<<" "<<a[i]<<endl; } //cout<<"?"; build(1,1,n); //for(int i=0;i<t[1].siz;i++) cout<<t[1].maxn[i]<<" "; //cout<<endl; while(q--){ cin>>op; if(!op){ int x,v; //cout<<"!!!!!"; cin>>x>>v; re(1,1,n,x,v); //for(int i=0;i<t[1].siz;i++) cout<<t[1].maxn[i]<<" "; //cout<<endl; } else{ int x,y; cin>>x>>y; k.siz=0; find(1,1,n,x,y); //cout<<k.siz<<endl; for(int i=2;i<k.siz;i++){ if(k.maxn[i]+k.maxn[i-1]>k.maxn[i-2]){ cout<<k.maxn[i]+k.maxn[i-1]+k.maxn[i-2]<<endl; break; } else if(i==k.siz-1){ cout<<0<<endl; break; } } } } }