#include<bits/stdc++.h> #define PII pair<int,int> #define fir first #define sec second #define mp make_pair #define endl '\n' using namespace std; const int LIM=50; const int maxn=2e5+7; const int INF=1e9; int n,q; int a[maxn]; #define lc(p) ((p)<<1) #define rc(p) ((p)<<1|1) struct SGT{ PII d[maxn<<2]; inline void Pu(int p){d[p]=max(d[lc(p)],d[rc(p)]);} inline void B(int p,int l,int r){ if(l==r){return void(d[p]=mp(a[l],l));} int mid=l+r>>1; B(lc(p),l,mid);B(rc(p),mid+1,r); Pu(p); } inline void U(int p,int l,int r,int x,int dt){ if(l==r)return void(d[p]=mp(dt,l)); int mid=l+r>>1; if(x<=mid)U(lc(p),l,mid,x,dt); else U(rc(p),mid+1,r,x,dt); Pu(p); } inline PII Qry(int p,int l,int r,int L,int R){ if((L<=l)&&(r<=R))return d[p]; int mid=l+r>>1; if(L<=mid&&R>mid)return max(Qry(lc(p),l,mid,L,R),Qry(rc(p),mid+1,r,L,R)); else if(L<=mid)return Qry(lc(p),l,mid,L,R); else if(R>mid)return Qry(rc(p),mid+1,r,L,R); } }T; inline int Get(vector<int> A){ int Siz=A.size(); for(int i=0;i<Siz-2;i++)if(A[i]<A[i+1]+A[i+2])return A[i]+A[i+1]+A[i+2]; return 0; } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifndef ONLINE_JUDGE freopen("triangle.in","r",stdin); freopen("triangle.out","w",stdout); #endif cin>>n>>q; for(int i=1;i<=n;i++)cin>>a[i]; T.B(1,1,n); while(q--){ int op,l,r; cin>>op>>l>>r; if(op==0)T.U(1,1,n,l,r); else{ PII MX=T.Qry(1,1,n,l,r); stack<PII> stk; while(!stk.empty())stk.pop(); vector<int> A;A.clear(); int cnt=0; int ret=0; while(MX.fir!=(int)-1e9&&cnt<LIM){ A.push_back(MX.fir); if(A.size()>=3){ if(A[A.size()-3]<A[A.size()-2]+A[A.size()-1]){ ret=A[A.size()-3]+A[A.size()-2]+A[A.size()-1]; break; } } stk.push(MX); T.U(1,1,n,MX.sec,(int)-1e9); MX=T.Qry(1,1,n,l,r); ++cnt; } while(!stk.empty()){ int p=stk.top().sec,v=stk.top().fir; T.U(1,1,n,p,v); stk.pop(); } cout<<ret<<endl; } } cout.flush(); }