#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)<(b)?(b):(a))
#define INF 0x3f3f3f3f
#define ll long long
#define sc scanf
#define pr printf
#define v1 first
#define v2 second
#define f(nm1,nm2,nm3) for(int nm1=nm2; nm1<= nm3; nm1++)
#define lowbit(x) (x&(-x))
#define int long long
#define lson k*2,l,mid
#define rson k*2+1,mid+1,r
const int sz=100005;
int nowl,nowr,lazy[sz*4],val[sz*4],a[sz],n,m,maxn[sz*4];
void build(int k,int l,int r)
{
    if(l==r)
    {
        val[k]=max(0,a[l]);
        maxn[k]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    val[k]=val[k*2]+val[k*2+1];
    maxn[k]=max(maxn[k*2],maxn[k*2+1]);
}

ll query(int k,int l,int r)
{
    if(nowl<=l&&r<=nowr)
        return val[k];
    int mid=(l+r)>>1,ans=0;
    if(nowl<=mid)
        ans+=query(lson);
    if(nowr>mid)
        ans+=query(rson);
    return ans;
}
ll query2(int k,int l,int r)
{
    if(nowl<=l&&r<=nowr)
        return maxn[k];
    int mid=(l+r)>>1,ans=-1e18;
    if(nowl<=mid)
        ans=max(ans,query2(lson));
    if(nowr>mid)
        ans=max(ans,query2(rson));
    return ans;
}
void add(int k,int l,int r,int x)
{
    if(nowl<=l&&r<=nowr)
    {
        maxn[k]=x;
        val[k]=max(x,0);
        return;
    }
    int mid=(l+r)>>1;
    if(nowl<=mid)
        add(lson,x);
    if(nowr>mid)
        add(rson,x);
    val[k]=val[k*2]+val[k*2+1];
    maxn[k]=max(maxn[k*2],maxn[k*2+1]);
}
signed main()
{
    sc("%lld%lld",&n,&m);
    for(int i=1; i <= n; i++)
        sc("%lld",&a[i]);
    build(1,1,n);
    while(m--)
    {
        int op;
        sc("%lld%lld%lld",&op,&nowl,&nowr);
        if(op==1)
        {
            if(nowl>nowr)
                swap(nowl,nowr);
            int res1=query(1,1,n);
            int res2=query2(1,1,n);
            if(res2<0)
                pr("%lld\n",res2);
            else
                pr("%lld\n",res1);
        }
        else
        {
            int s=nowr;
            nowr=nowl;
            add(1,1,n,s);
        }
    }
    return 0;
}