/*

    |-------|  |-------|  |-------|  |-------|  |
    |          |       |          |  |       |  |
    |          |       |          |  |       |  |
    |-------|  |-------|          |  |-------|  |
            |  |       |  |---|   |  |       |  |
            |  |       |  |       |  |       |  |
    |-------|  |       |  |-------|  |       |  |-------|

*/

#include <bits/stdc++.h>

using namespace std;

#define read freopen("in.txt", "r", stdin)
#define INF(ar) memset(ar,126,sizeof ar)
#define SET(ar) memset(ar,-1,sizeof ar)
#define rep(i,n) for(int i=0;i<(n);i++)
#define CLR(ar) memset(ar,0,sizeof ar)
#define din(a) scanf("%lf",&a)
#define lin(a) scanf("%lld",&a)
#define win(s) scanf("%s",s)
#define iin(a) scanf("%d",&a)
#define all(x) x.begin(),x.end()
#define vlong long long
#define linf (1LL<<62)
#define pi 2*acos(0.0)
#define pb push_back
#define mp make_pair
#define inf (1<<30)
#define xx first
#define yy second

//int dx[]={1,0,-1,0};                  int dy[]={0,1,0,-1};                // 4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};        int dy[]={0,1,1,1,0,-1,-1,-1};      // 8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};       int dy[]={1,2,2,1,-1,-2,-2,-1};     // Knight Direction
//int dx[]={-1,-1,+0,+1,+1,+0};         int dy[]={-1,+1,+2,+1,-1,-2};       // Hexagonal Direction

int setBit(int n,int pos){return n|(1<<pos);}
int resetBit(int n,int pos){return n&~(1<<pos);}
bool checkBit(int n,int pos){return n&(1<<pos);}
inline vlong bigmod(vlong p,vlong e,vlong M){vlong ret=1;while(e>0){if(e%2)ret=(ret*p)%M;p=(p*p)%M;e/=2;}return ret;}
inline vlong power(vlong x,vlong y){vlong ans=1;while(y>0){if(y%2)ans*=x;x*=x;y/=2;}return ans;}
template<class T> T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<class T> T lcm(T a,T b){return a*(b/gcd(a,b));}

struct node
{
    int lmax, rmax, tsum, mmax;
};

node t[3*50005];
int n, q, a[50005];

node marge(node l, node r)
{
    node temp;
    temp.lmax = max(l.lmax, l.tsum+r.lmax);
    temp.rmax = max(r.rmax, r.tsum+l.rmax);
    temp.mmax = max(max(l.mmax, r.mmax), l.rmax+r.lmax);
    temp.tsum = l.tsum+r.tsum;
    return temp;
}

node makeNode(int a, int b, int c, int d)
{
    node temp;
    temp.lmax = a;
    temp.rmax = b;
    temp.mmax = c;
    temp.tsum = d;
    return temp;
}

void update(int num, int st, int ed, int in, int v)
{
    if(in < st || in > ed)
    {
        return;
    }
    if(st == ed)
    {
        t[num] = makeNode(v, v, v, v);
        return;
    }
    int mid = (st+ed)/2;
    update(num<<1, st, mid, in, v);
    update(num<<1|1, mid+1, ed, in, v);
    t[num] = marge(t[num<<1], t[num<<1|1]);
}

node query(int num, int st, int ed, int i, int j)
{
    if(j < st || i > ed)
    {
        return makeNode(-(1<<30), -(1<<30), -(1<<30), -(1<<30));
    }
    if(st >= i && ed <= j)
    {
        /// printf("%d %d\n", num, t[num].mmax);
        return t[num];
    }
    int mid = (st+ed)/2;
    /// printf("%d %d\n", num, m.mmax);
    return marge(query(num<<1, st, mid, i, j), query(num<<1|1, mid+1, ed, i, j));
}

void build(int num, int st, int ed)
{
    if(st == ed)
    {
        t[num] = makeNode(a[st], a[st], a[st], a[st]);
        /// printf("%d %d\n", num, t[num].mmax);
        return;
    }
    int mid = (st+ed)/2;
    build(num<<1, st, mid);
    build(num<<1|1, mid+1, ed);
    t[num] = marge(t[num<<1], t[num<<1|1]);
    /// printf("%d %d\n", num, t[num].mmax);
}

int main()
{
    iin(n);
    rep(i, n)
    {
        iin(a[i + 1]);
    }
    build(1, 1, n);
    iin(q);
    rep(i, q)
    {
        int c, x, y;
        iin(c);
        if(c == 0)
        {
            iin(x); iin(y);
            update(1, 1, n, x, y);
        }
        else
        {
            iin(x); iin(y);
            printf("%d\n", query(1, 1, n, x, y).mmax);
        }
    }
}