#include <cstdio>
#include <algorithm>
#define FIN "maxq.in"
#define FOUT "maxq.out"
#define NM (1<<18)
using namespace std;
#define max(a, b) ((a) > (b) ? (a) : (b))
int N, M;
int v[NM];
long long A[3*NM], B[3*NM], C[3*NM], Sum[3*NM];
int ThePosition, TheValue;
void build(int E, int Left, int Right){
	if (Left == Right) {
		A[E] = B[E] = C[E] = max(v[Left], 0);
		Sum[E] = v[Left];
		return;
	}
	int Middle=(Left+Right)>>1,left=E<<1,right=left+1;
        build(left,Left,Middle);
	    build(right, Middle+1,Right);
    A[E] = max(A[left], Sum[left]+A[right]);
	B[E] = max(B[left]+Sum[right], B[right]);
	C[E] = max(max(C[left], C[right]), B[left]+A[right]);
    Sum[E] = Sum[left]+Sum[right];
}
void update(int E, int Left, int Right){
	if (Left == Right) {
		A[E] = B[E] = C[E] = max(TheValue, 0);
		Sum[E] = TheValue;
		return;
	}
	int Middle=(Left+Right)>>1,left=E<<1,right=left+1;
	if (ThePosition <= Middle)
        update(left,Left,Middle);
	else
	    update(right, Middle+1,Right);
    A[E] = max(A[left], Sum[left]+A[right]);
	B[E] = max(B[left]+Sum[right], B[right]);
	C[E] = max(max(C[left], C[right]), B[left]+A[right]);
    Sum[E] = Sum[left]+Sum[right];
}
int Start, Finish;
long long ans, S;
void query(int E, int Left, int Right){
	if (Start <= Left && Right <= Finish) {
		if (S < 0)
            S = 0;
		ans = max(ans, max(S+A[E], C[E]));
		S = max(S+Sum[E], B[E]);
		return;
	}
	int Middle=(Left+Right)>>1;
	if (Start <= Middle)  query(E<<1,Left,Middle);
	if (Middle < Finish) query((E<<1)|1, Middle+1,Right);
}
int main(){
	int i, t, v1, v2;
	freopen(FIN,"r",stdin);
	freopen(FOUT,"w",stdout);
	scanf("%d", &N);
	for (i = 1; i <= N; ++i){
		scanf("%d", v+i);
	}
	build(1,1,N);
	scanf("%d", &M);
	while (M--) {
		scanf("%d %d %d", &t, &v1, &v2);
		if (t == 0) {
			ThePosition = v1+1;
			TheValue = v2;
			update(1, 1, N);
		}
		else {
			S = ans = 0;
			Start = v1+1;
			Finish = v2+1;
			query(1, 1, N);
			printf("%lld\n", ans);
		}
	}
	return 0;
}