#include <cstdio>
#include <algorithm>
#define Nmax 100005

using namespace std;

int maxim[3*Nmax],s[3*Nmax],N,a[Nmax];

inline void Update(int nod, int st, int dr, int x, int y)
{
    if(st==dr)
    {
        s[nod]=maxim[nod]=y;
        return;
    }
    int mij=(st+dr)/2;
    if(x<=mij)
        Update(2*nod,st,mij,x,y);
    else
        Update(2*nod+1,mij+1,dr,x,y);
    s[nod]=s[2*nod]+s[2*nod+1];
    maxim[nod]=max(maxim[2*nod+1],maxim[2*nod]-s[2*nod+1]);
}

inline int Maxim(int nod, int st, int dr, int x, int y, int ok)
{
    if(st==x && dr==y)
    {
        if(ok)
            return maxim[nod];
        else
            return s[nod];
    }
    int mij=(st+dr)/2;
    if(y<=mij)
        return Maxim(2*nod,st,mij,x,y,1);
    else
        if(x>mij)
            return Maxim(2*nod+1,mij+1,dr,x,y,1);
        else
            return max(Maxim(2*nod+1,mij+1,dr,mij+1,y,1),Maxim(2*nod,st,mij,x,mij,1)-Maxim(2*nod+1,mij+1,dr,mij+1,y,0));
}

int main()
{
    int i,x,y,z,sol,st,dr,mij,M;
    freopen ("arbint.in","r",stdin);
    freopen ("arbint.out","w",stdout);
    scanf("%d%d", &N,&M);
    for(i=1;i<=N;++i)
    {
        scanf("%d", &x);
        a[i]=x;
        Update(1,1,N,i,x);
    }
    while(M--)
    {
        scanf("%d%d%d", &x,&y,&z);
        if(x)
        {
            Update(1,1,N,y,z);
            a[y]=z;
        }
        else
        {
            printf("%d\n", Maxim(1,1,N,x,z,1));
        }
    }
    return 0;
}