#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n,q; int a[N],op,l,r; priority_queue<int> pq; int f,s,t; signed main(){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); while(q--){ while(!pq.empty()) pq.pop(); scanf("%d%d%d",&op,&l,&r); if(op){ for(int i=l;i<=r;i++){ pq.push(a[i]); } f=pq.top(); pq.pop(); s=pq.top(); pq.pop(); t=pq.top(); pq.pop(); while(s+t<=f&&!pq.empty()){ f=s; s=t; t=pq.top(); pq.pop(); } if(s+t>f){ printf("%d\n",s+t+f); }else{ printf("0\n"); } }else{ a[l]=r; } } return 0; }