#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int LIM=48; const int maxn=2e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,q,a[maxn]; #define poly vector<int> int W[maxn]; poly operator+(poly a,poly b){ poly vec; int len=0; int i=0,j=0; while((i<int(a.size())||j<int(b.size()))&&len<LIM){ if(i==int(a.size()))W[len++]=b[j++]; else if(j==int(b.size()))W[len++]=a[i++]; else if(a[i]>b[j])W[len++]=a[i++]; else W[len++]=b[j++]; }vec.resize(len); up(i,0,len-1)vec[i]=W[i]; return vec; } struct SegTree { poly v[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void pu(int p){v[p]=v[ls(p)]+v[rs(p)];} void bd(int l,int r,int p){ if(l==r){ v[p].p_b(a[l]);return; }int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(p); }void modify(int l,int s,int t,int p,int x){ if(s==t){v[p].clear();v[p].p_b(x);return;} int mid=s+t>>1; if(l<=mid)modify(l,s,mid,ls(p),x);else modify(l,mid+1,t,rs(p),x);pu(p); } poly qry(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return v[p]; int mid=s+t>>1; if(r<=mid)return qry(l,r,s,mid,ls(p)); if(l>mid)return qry(l,r,mid+1,t,rs(p)); return qry(l,r,s,mid,ls(p))+qry(l,r,mid+1,t,rs(p)); } }T; int get_ans(poly a){ reverse(a.begin(),a.end()); int sz=a.size(),res=0; up(i,0,sz-3){ int pos=lower_bound(a.begin(),a.end(),a[i]+a[i+1])-a.begin()-1; if(pos>=i+2)res=max(res,a[i]+a[i+1]+a[pos]); }return res; } void slv(){ n=read(),q=read(); up(i,1,n)a[i]=read(); T.bd(1,n,1); while(q--){ int op=read(),x=read(),v=read(); if(op==0)T.modify(x,1,n,1,v); else printf("%d\n",get_ans(T.qry(x,v,1,n,1))); } } int main(){ //freopen("triangle.in","r",stdin); //freopen("triangle.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }