#include <algorithm>
#include <fstream>
#define N (1<<18)
using namespace std;
ifstream fin("maxq.in");
ofstream fout("maxq.out");

int n,m;
int v[N];
long long A[N<<1], B[N<<1], C[N<<1], Sum[N<<1];

#define lf (n<<1)
#define rt (lf+1)
#define md ((l+r)>>1)

void Build(int n, int l, int r)
{
    if (l==r)
    {
        A[n]=B[n]=C[n]=max(v[l],0);
        Sum[n]=v[l];
    }
    else
    {
      Build(lf,l,md);
      Build(rt, md+1, r);
      A[n]=max(A[lf], Sum[lf]+A[rt]);
      B[n]=max(B[lf]+Sum[rt],B[rt]);
      C[n]=max(max(C[lf], C[rt]),B[lf]+A[rt]);
      Sum[n]=Sum[lf]+Sum[rt];
    }
}
int p,x;
void Update(int n, int l, int r)
{
    if(l==r){
        A[n]=B[n]=C[n]=max(x,0);
        Sum[n]=x;
    }
    else{
        if(p<=md)Update(lf,l,md);
        else Update(rt,md+1,r);
      A[n]=max(A[lf], Sum[lf]+A[rt]);
      B[n]=max(B[lf]+Sum[rt],B[rt]);
      C[n]=max(max(C[lf], C[rt]),B[lf]+A[rt]);
      Sum[n]=Sum[lf]+Sum[rt];
    }
}

int a, b;
long long sol, S;
void Query(int n, int l, int r)
{
    if(a<=l && r<=b)
    {
        if(S<0) S=0;
        sol=max(sol, max(S+A[n],C[n]));
        S=max(S+Sum[n], B[n]);
    }
    else{
        if(a<=md) Query(lf,l,md);
        if(b>md) Query(rt,md+1,r);
    }
}

int main()
{
    int i,t, v1,v2;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    Build(1,1,n);
    fin>>m;
    while(m--)
    {
        fin>>t>>v1>>v2;
        if(t==0)
        {
            p=v1+1;
            x=v2;
            Update(1,1,n);
        }
        else
        {
            S=sol=0;
            a=v1+1;
            b=v2+1;
            Query(1,1,n);
            fout<<sol<<"\n";
        }
    }
    return(0);
}