#include<fstream>
#define nmax 60006
#define max(a,b) (a > b ? a : b)
#define min(a,b) (a > b ? b : a)
#define nod_st (nod * 2)
#define nod_dr (nod * 2 + 1)
#define ll long long
using namespace std;

ifstream fin("datorii.in");
ofstream fout("datorii.out");

long long  N, start, finish, v[nmax], poz, val, S, maxi;
ll F[nmax];//suma max a primelor elemente din interval
ll L[nmax];//suma max a ultimelor elemente din interval
ll sum[nmax];//suma toatala
ll M[nmax];//suma maxima oriunde in interval

void update(int nod, int st, int dr)
{
     if(st == dr)//se ajunge in nod elementar
     {
         F[nod] = L[nod] = M[nod] = max(0, v[st]);
         sum[nod] = v[st];
         return;

     }
     int mij = (st + dr)/2;
     update(nod_st, st, mij);
     update(nod_dr, mij + 1, dr);
     //acum construim F ,L, M si sum nu ajutorul celor doi fii deja completati
     F[nod] = max(F[nod_st], sum[nod_st] + F[nod_dr]); //suma maxima din prima parte a intervalului = S din prima a parte a fiului stang ori tot fiul stang + prima parte din nodul drept
     L[nod] = max(L[nod_dr], sum[nod_dr] + L[nod_st]);//la fel pt last
     M[nod] = max(M[nod_st], max(M[nod_dr] , L[nod_st] + F[nod_dr]));
     sum[nod] = sum[nod_st] + sum[nod_dr];

}

void change(int nod, int st, int dr)
{
    if(st == dr)
    {
         F[nod] = L[nod] = M[nod] = max(0, val);
         sum[nod] = val;
         return;
    }
    int mij = (st + dr) / 2;
    if(mij >= poz)  change(nod_st, st, mij);
        else
           change(nod_dr, mij + 1, dr);
    F[nod] = max(F[nod_st], sum[nod_st] + F[nod_dr]); //suma maxima din prima parte a intervalului = S din prima a parte a fiului stang ori tot fiul stang + prima parte din nodul drept
     L[nod] = max(L[nod_dr], sum[nod_dr] + L[nod_st]);//la fel pt last
     M[nod] = max(M[nod_st], max(M[nod_dr] , L[nod_st] + F[nod_dr]));
     sum[nod] = sum[nod_st] + sum[nod_dr];
}

void query(int nod, int st, int dr)
{
    if(start <= st && dr <= finish)//intervalele sunt disjuncte si sunt parcurse de la st la dreapta
    {
        if(S < 0 )
            S = 0;
        maxi = max( maxi, max(S + F[nod] , M[nod]));
        S = max(S + sum[nod], L[nod]);
        return ;
    }
    int mij = (st +dr)/2;
    if(start <= mij)   query(nod_st, st, mij);
    if(finish > mij)   query(nod_dr, mij + 1, dr);

}
void read()
{
    int nr;
    fin>> N >>nr;
    for(int i = 1; i <= N;i++)
        fin >>v[i];
    update(1, 1, N);

    for(int i = 1; i <= nr; i++)
    {
        int tip;
        fin >>tip;
        if( tip == 0)
        {
            fin >> poz>> val;
            val = v[poz] - val;
            change(1,1,N);
        }
        if(tip == 1)
        {
            fin>>start >> finish;
            maxi = -1000;
            S = 0;
            query(1, 1, N);
            fout << maxi <<'\n';

        }
    }

}
int main()
{
    read();
    fin.close();
    return 0;
}