#include <bits/stdc++.h>
using namespace std;

ifstream f("maxq.in");
ofstream g("maxq.out");

struct arb
{
    long long prefix, sufix, s_tot, rez;
//    arb()
//    {
//        prefix=sufix=s_tot=rez=0;
//    }
//    arb(long long a, long long b, long long c, long long d)
//    {
//        prefix=a;
//        sufix=b;
//        s_tot=c;
//        rez=d;
//    }
} tree[800005];

long long n, x, m, tip, a, b;

void update_tree(long long st, long long dr, long long ind_tree, long long ind_dorit, long long val)
{
    if (st==dr)
    {
        tree[ind_tree].prefix=tree[ind_tree].sufix=tree[ind_tree].s_tot=tree[ind_tree].rez=val;
        return;
    }
    long long mij=(st+dr)/2;
    if (mij>=ind_dorit)
    {
        update_tree(st,mij,ind_tree*2,ind_dorit,val);
    }
    else
        update_tree(mij+1,dr,ind_tree*2+1,ind_dorit,val);
    tree[ind_tree].prefix=max(tree[ind_tree*2].prefix,tree[ind_tree*2].s_tot+tree[ind_tree*2+1].prefix);
    tree[ind_tree].sufix=max(tree[ind_tree*2+1].sufix, tree[ind_tree*2+1].s_tot+tree[ind_tree*2].sufix);
    tree[ind_tree].s_tot=tree[ind_tree*2].s_tot+tree[ind_tree*2+1].s_tot;
    tree[ind_tree].rez=max(max(tree[ind_tree*2].rez,tree[ind_tree*2+1].rez),tree[ind_tree*2].sufix+tree[ind_tree*2+1].prefix);
}

arb query(long long st, long long dr, long long ind_tree, long long st_q, long long dr_q)
{
    if (st>dr_q || dr<st_q)
    {
        return {-0x3f3f3f3f, -0x3f3f3f3f, -0x3f3f3f3f, -0x3f3f3f3f};
    }
    if (st>=st_q && dr<=dr_q)
        return tree[ind_tree];
    long long mij=(st+dr)/2;
    arb treest=query(st,mij,ind_tree*2,st_q,dr_q);
    arb treedr=query(mij+1,dr,ind_tree*2+1,st_q,dr_q);
    arb x;
    x.prefix=max(treest.prefix,treest.s_tot+treedr.prefix);
    x.sufix=max(treedr.sufix,treedr.s_tot+treest.sufix);
    x.s_tot=treest.s_tot+treedr.s_tot;
    x.rez=max(max(treest.rez,treedr.rez),treest.sufix+treedr.prefix);
    return x;
}

long long main()
{
    f >> n;
    for (long long i=1; i<=n; ++i)
    {
        f >> x;
        update_tree(1,n,1,i,x);
    }
    f >> m;
    while (m--)
    {
        f >> tip >> a >> b;

        if (tip==0)
        {
            a++;
            update_tree(1,n,1,a,b);

        }
        else
        {
            a++;
            b++;
            g << query(1,n,1,a,b).rez << '\n';
        }
    }

    return 0;
}