#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 #define poly vector<int> 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]; struct SegTree { pi v[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void pu(int p){v[p]=max(v[ls(p)],v[rs(p)]);} void bd(int l,int r,int p){ if(l==r){ v[p]=m_p(a[l],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]=m_p(x,l);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); } pi 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 max(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 { poly a;vector<pi>vec; while(int(vec.size())<LIM){ auto it=T.qry(x,v,1,n,1); if(it.p1<0)break; vec.p_b(it); a.p_b(it.p1); T.modify(it.p2,1,n,1,-1e9); if(a.size()>=3){ int sz=a.size()-1; if(a[sz-2]<a[sz]+a[sz-1])break; } } printf("%d\n",get_ans(a)); for(auto it:vec)T.modify(it.p2,1,n,1,it.p1); } } } int main(){ //freopen("triangle.in","r",stdin); //freopen("triangle.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }