#include<bits/stdc++.h>
#define LL long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=5e5+10;
struct Node
{
int l,r;
int tmax,lmax,rmax,sum;
}tr[N*4];
int w[N];
int n,m;
void pushup(Node &u,Node &l,Node &r)
{
u.sum=l.sum+r.sum;
u.rmax=max(r.rmax,l.rmax+r.sum);
u.lmax=max(l.lmax,l.sum+r.lmax);
u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}
void pushup(int u)
{
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u]={l,r,w[r],w[r],w[r],w[r]};
return;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int x,int v)
{
if(tr[u].l==x&&tr[u].r==x)
{
tr[u]={x,x,v,v,v,v};
return;
}
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid)modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(u);
}
Node query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)return tr[u];
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid)return query(u<<1,l,r);
if(l>mid)return query(u<<1|1,l,r);
auto left=query(u<<1,l,r);
auto right=query(u<<1|1,l,r);
Node res;
pushup(res,left,right);
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
build(1,1,n);
while(m--)
{
int k,x,y;
cin>>k>>x>>y;
if(k==1)
{
if(x>y)swap(x,y);
cout<<query(1,x,y).tmax<<endl;
}
else modify(1,x,y);
}
return 0;
}