#include<bits/stdc++.h> using namespace std; #define ls pos<<1 #define rs pos<<1|1 #define int long long const int N=2e5+10; int n,q,a[N]; struct Node{int x[60];}t[N<<2]; int read(){ char c=getchar();bool op=0; if(c=='-')op=1; while(c>'9'||c<'0')c=getchar(); int d=0; while(c>='0'&&c<='9'){d=d*10+c-'0';c=getchar();} if(op)return -d; return d; } void pushup(int pos){ int i=1,j=1; while(i+j-1<=50){ if(t[ls].x[i]>=t[rs].x[j]&&i<=50){t[pos].x[i+j-1]=t[ls].x[i];i++;} else{t[pos].x[i+j-1]=t[rs].x[j];j++;} } } void build(int pos,int l,int r){ // cout<<pos<<" "<<l<<" "<<r<<endl; if(l==r){t[pos].x[1]=a[l];return;} int mid=(l+r)>>1; build(ls,l,mid);build(rs,mid+1,r); pushup(pos); } void modify(int pos,int l,int r,int x,int k){ if(l==r){t[pos].x[1]=k;return;} int mid=(l+r)>>1; if(x<=mid)modify(ls,l,mid,x,k); else modify(rs,mid+1,r,x,k); pushup(pos); } Node query(int pos,int l,int r,int ql,int qr){ if(l>=ql&&r<=qr){return t[pos];} int mid=(l+r)>>1;Node res,p,q; for(int i=1;i<=50;i++)p.x[i]=q.x[i]=0; if(ql<=mid)p=query(ls,l,mid,ql,qr); if(qr>mid)q=query(rs,mid+1,r,ql,qr); int i=1,j=1; while(i+j-1<=50){ if(p.x[i]>=q.x[j]&&i<=50){res.x[i+j-1]=p.x[i];i++;} else{res.x[i+j-1]=q.x[j];j++;} } return res; } signed main(){ n=read();q=read(); for(int i=1;i<=n;i++)a[i]=read(); build(1,1,n); int op,x,y; while(q--){ op=read();x=read();y=read(); if(op==0){modify(1,1,n,x,y);} else{ Node ans=query(1,1,n,x,y); bool flag=0; for(int i=1;i<=48;i++){ if(ans.x[i+1]+ans.x[i+2]>ans.x[i]){ int ANS=ans.x[i]+ans.x[i+1]+ans.x[i+2]; printf("%lld\n",ANS);flag=1;break; } } if(!flag)printf("0\n"); } } return 0; }