#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+10;
int n,m;
int a[N];
struct node
{
    int l,r;
    ll ml,mr,ans,sum;
}tr[N*4];
void up(int k)
{
    tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
    tr[k].ml=max(tr[k<<1].ml,tr[k<<1].sum+tr[k<<1|1].ml);
    tr[k].mr=max(tr[k<<1|1].mr,tr[k<<1].mr+tr[k<<1|1].sum);
    tr[k].ans=max(max(tr[k<<1].ans,tr[k<<1|1].ans),tr[k<<1].mr+tr[k<<1|1].ml);
    return;
}
void build(int k,int l,int r)
{
    tr[k].l=l,tr[k].r=r;
    if(l==r)
    {
        tr[k].sum=tr[k].ans=tr[k].ml=tr[k].mr=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    up(k);
}
void change(int k,int p,int s)
{
    if(tr[k].l==tr[k].r)
    {
        tr[k].ans=tr[k].sum=tr[k].ml=tr[k].mr=s;
        return;
    }
    int mid=(tr[k].l+tr[k].r)>>1;
    if(p<=mid)
        change(k<<1,p,s);
    else if(p>mid)
        change(k<<1|1,p,s);
    up(k);
}
node ask(int k,int a,int b)
{
    if(tr[k].l>=a && tr[k].r<=b)
        return tr[k];
    int mid=(tr[k].l+tr[k].r)>>1;
    if(b<=mid)//区间全在左儿子里
        return ask(k<<1,a,b);
    else{
        if(a>mid)//访问的区间全在右儿子
            return ask(k<<1|1,a,b);
        else//(左右两边都有，从中间截断)
        {//参考up操作
            node t;
            node aa=ask(k<<1,a,b),bb=ask(k<<1|1,a,b);
            t.ml=max(aa.ml,aa.sum+bb.ml);
            t.mr=max(bb.mr,aa.mr+bb.sum);
            t.ans=max(max(aa.ans,bb.ans),bb.mr+aa.ml);
            return t;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        int k,a,b;
        cin>>k>>a>>b;
        if(k==1)
        {
            if(a>b)
                swap(a,b);
            cout<<ask(1,a,b).ans<<"\n";
        }
        else if(k==2)
            change(1,a,b);
    }
    return 0;
}