#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>

using namespace std;

typedef long long llint;

#define INF 0x3f3f3f3f
#define MAXN 50005

struct Node {
    int q, lsum, rsum, sum;
} node[4*MAXN];

void Update ( int v, int x, int y, int pos, int val ) {
    int mid = (x+y)/2;

    if ( x == y ) {
        node[v].q = node[v].lsum = node[v].rsum = node[v].sum = val;
        return;
    }
    if ( pos <= mid ) {
        Update ( 2*v, x, mid, pos, val );
    }
    else {
        Update ( 2*v+1, mid+1, y, pos, val );
    }
    node[v].q = max ( max ( node[2*v].q, node[2*v+1].q ), node[2*v].rsum + node[2*v+1].lsum );
    node[v].sum = node[2*v].sum + node[2*v+1].sum;
    node[v].lsum = max ( node[2*v].lsum, node[2*v].sum + node[2*v+1].lsum );
    node[v].rsum = max ( node[2*v+1].rsum, node[2*v+1].sum + node[2*v].rsum );
}

Node Query ( int v, int x, int y, int Qx, int Qy ) {
    int mid = (x+y)/2;

    if ( x==Qx && y==Qy ) {
        return node[v];
    }

    if ( Qy <= mid ) {
        return ( Query ( 2*v, x, mid, Qx, Qy ) );
    }
    if ( Qx > mid ) {
        return ( Query ( 2*v+1, mid+1, y, Qx, Qy ) );
    }
    Node o1, o2, o3;

    o1 = Query ( 2*v, x, mid, Qx, mid );
    o2 = Query ( 2*v+1, mid+1, y, mid+1, Qy );

    o3.q = max ( max ( o1.q, o2.q ), o1.rsum + o2.lsum );
    o3.lsum = max ( o1.lsum, o1.sum + o2.lsum );
    o3.rsum = max ( o2.rsum, o2.sum + o1.rsum );
    o3.sum = o1.sum + o2.sum;

    return o3;
}
    

int main ( void ) {
	//freopen (".in","r",stdin); freopen(".out","w",stdout);
    int i, tmp, tmp1, tmp2, N, M;

    scanf ("%d", &N);
    for ( i=1; i<=N; ++i ) {
        scanf ("%d", &tmp);
        Update ( 1, 1, N, i, tmp );
    }
    scanf ("%d", &M);
    for ( i=1; i<=M; ++i ) {
        scanf ("%d %d %d", &tmp, &tmp1, &tmp2 );
        if ( tmp == 0 ) {
            Update ( 1, 1, N, tmp1, tmp2 );
        }
        else {
            printf ("%d\n",( Query ( 1, 1, N, tmp1, tmp2 ) ).q );
        }
    }

	return (0);
}