#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define ctz __builtin_ctz using namespace std; const int N=2e5+10; int tmp[N]; int a[N];int n,q; struct ask{ int op,l,r; }Q[N]; int calc(vector<int> x){ int tp=0; sort(x.begin(),x.end()); int ans=0,sz=x.size(); //for(auto ed:x) cout<<ed<<' '; for(int i=2;i<sz;i++){ if(x[i-1]+x[i-2]>x[i]) ans=max(ans,x[i]+x[i-1]+x[i-2]); }return ans; }int LM=60; bool cmp(int a,int b){ return a>b; } struct sgt{ vector<int> mg(vector<int> a,vector<int> b){ vector<int> x;x.clear(); for(auto ed:b) a.push_back(ed); sort(a.begin(),a.end(),cmp); int sz=a.size();sz=min(sz,LM); for(int i=0;i<sz;i++) x.push_back(a[i]); return x; }vector<int> T[N<<2+1]; #define ls p*2 #define rs p*2+1 #define mid (l+r)/2 void pu(int p){ T[p]=mg(T[ls],T[rs]); }void bd(int p,int l,int r){ //cout<<l<<' '<<r<<endl; if(l==r){ T[p].push_back(a[l]);return ; }bd(ls,l,mid);bd(rs,mid+1,r);pu(p); }void upd(int p,int l,int r,int x,int v){ if(l==r){ T[p][0]=v;return ; }if(x<=mid) upd(ls,l,mid,x,v); else upd(rs,mid+1,r,x,v);pu(p); }vector<int> qry(int p,int l,int r,int pl,int pr){ if(pl<=l&&r<=pr) return T[p]; vector<int> x;x.clear(); if(pl<=mid) x=mg(x,qry(ls,l,mid,pl,pr)); if(pr>mid) x=mg(x,qry(rs,mid+1,r,pl,pr)); return x; } }sgt; void slv(){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sgt.bd(1,1,n); for(int i=1;i<=q;i++){ int op,l,r;scanf("%d%d%d",&op,&l,&r); if(op==0){ sgt.upd(1,1,n,l,r); }else{ printf("%d\n",calc(sgt.qry(1,1,n,l,r))); } } } int main(){ slv(); return 0; }