#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010;
int n,m;
struct node{
int l,r;
int sum;
int tmax;
int lmax,rmax;
}tr[N * 4];
int a[N];
void pushup(node &u,node &l,node &r){
u.sum = l.sum + r.sum;
u.lmax = max(l.sum + r.lmax,l.lmax);
u.rmax = max(r.sum + l.rmax,r.rmax);
u.tmax = max(max(l.tmax,r.tmax),l.rmax + r.lmax);
}
void build(int u,int l,int r){
if(l == r) tr[u] = {l,r,a[l],a[l],a[l],a[l]};
else{
tr[u] = {l,r};
int mid = l + r >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
pushup(tr[u],tr[u << 1],tr[u << 1 | 1]);
}
}
node query(int u,int l,int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u];
else{
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query(u << 1,l,r);
else if(l > mid) return query(u << 1 | 1,l,r);
else{
auto L = query(u << 1,l,r);
auto R = query(u << 1 | 1,l,r);
node ans;
pushup(ans,L,R);
return ans;
}
}
}
void modify(int u,int x,int k){
if(tr[u].l == x && tr[u].r == x) tr[u] = {x,x,k,k,k,k};
else{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1,x,k);
else modify(u << 1 | 1,x,k);
pushup(tr[u],tr[u << 1],tr[u << 1 | 1]);
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
while(m -- ){
int k,x,y;
scanf("%d %d %d",&k,&x,&y);
if(k == 1){
if(x > y) swap(x,y);
printf("%d\n",query(1,x,y).tmax);
}
else{
modify(1,x,y);
}
}
return 0;
}