#include<bits/stdc++.h> using namespace std; const int LIM=50; const int maxn=2e5+7; int n,q; int a[maxn]; vector<int> operator+(vector<int> A,vector<int> B){ vector<int> ret; ret.clear(); int cnt=0; int AC=0,BC=0; while(cnt<LIM){ if((AC==A.size())&&(BC==B.size()))break; else if(AC==A.size()){ret.push_back(B[BC++]);++cnt;continue;} else if(BC==B.size()){ret.push_back(A[AC++]);++cnt;continue;} else if(A[AC]>=B[BC]){ret.push_back(A[AC++]);++cnt;continue;} else {ret.push_back(B[BC++]);++cnt;continue;} } return ret; } vector<int> Init(int v){ vector<int> ret;ret.clear();ret.push_back(v); return ret; } #define lc(p) ((p)<<1) #define rc(p) ((p)<<1|1) struct SGT{ vector<int> d[maxn<<2]; inline void Pu(int p){d[p]=d[lc(p)]+d[rc(p)];} inline void B(int p,int l,int r){ if(l==r){return void(d[p]=Init(a[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]=Init(dt)); 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 vector<int> 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 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(){ #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{ vector<int> vec=T.Qry(1,1,n,l,r); cout<<Get(vec)<<endl; } } }