#include <bits/stdc++.h>
#define NMAX 200005
#define INF 1e9
using namespace std;

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

struct smx{

int s,l,r,m;

};

smx V[4*NMAX];
int C[NMAX],Sol,S;

void buildtree(int nod,int L,int R){
    if(L == R){
        V[nod].l = V[nod].m = V[nod].s = V[nod].r = C[L];
        return;
    }

    int mid = (L + R)/2;

    buildtree(2 * nod,L,mid);
    buildtree(2 * nod + 1, mid + 1,R);

    V[nod].s = V[2 * nod].s + V[2 * nod + 1].s;
    V[nod].l = max(V[2 * nod].l,V[2 * nod].s + V[2 * nod + 1].l);
    V[nod].r = max(V[2 * nod + 1].r,V[2 * nod + 1].r + V[2 * nod].r);
    V[nod].m = max(max(V[2 * nod].m,V[2 * nod + 1].m), V[2 * nod].r + V[2 * nod + 1].l);

}

void update(int nod,int L,int R,int p,int val){

    if(L == R && L == p){
        V[nod].l = V[nod].m = V[nod].s = V[nod].r = val;
        return;
    }
    int mid = (L + R);
    if(p <= mid)
        update(2 * nod,L,mid,p,val);
    else
        update(2 * nod + 1,mid + 1,R,p,val);

    V[nod].s = V[2 * nod].s + V[2 * nod + 1].s;
    V[nod].l = max(V[2 * nod].l,V[2 * nod].s + V[2 * nod + 1].l);
    V[nod].r = max(V[2 * nod + 1].r,V[2 * nod + 1].r + V[2 * nod].r);
    V[nod].m = max(max(V[2 * nod].m,V[2 * nod + 1].m), V[2 * nod].r + V[2 * nod + 1].l);

}

void query(int nod,int L,int R,int m,int M){
    if(L >= m && R <= M){
        Sol = max(Sol,max(V[nod].m,S + V[nod].l));
        S = max(S + V[nod].s, V[nod].r);
        return;
    }
    int mid = (L + R)/2;
    if(m <= mid)
        query(2 * nod,L,mid,m,M);
    if(mid < M)
        query(2 * nod + 1,mid + 1,R,m,M);

}

int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int n,m,q,x,y;

    fin >> n;

    for(int i = 1; i <= n; i++)
        fin >> C[i];

    buildtree(1,1,n);

    fin >> n;

    for(int i = 1; i <= m; i++){
        fin >> q >> x >> y;

        if(q == 0)
            update(1,1,n,x,y);
        else{
            Sol = INF;
            S = 0;
            query(1,1,n,x,y);
            fout << Sol << "\n";
        }

    }



    return 0;
}