#include<bits/stdc++.h>
// #define int long long
#define N 110000
using namespace std;
int s[N];
const int inf = (1<<29);
struct MM {
    int a[4][4];
    MM() {
        memset(a,0,sizeof(a));
    }
    MM operator*(const MM &b) const {
        MM res;
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
                for (int k = 1; k <= 3; k++)
                    res.a[i][j]=max(res.a[i][j],a[i][k]+b.a[k][j]);
        return res;
    }
} sum[N<<2];
int n,m,yuan;
void xg(int L,int R,int now,int x,int id) {
	int mid=(L+R)/2;
	if(L==R) {
		sum[id].a[2][1]=x;
		sum[id].a[2][2]=x;
		return;
	}
	if(now<=mid) xg(L,mid,now,x,id*2);
	if(now> mid) xg(mid+1,R,now,x,id*2+1);
	sum[id]=sum[id<<1]*sum[id<<1|1];
}
MM query(int L,int R,int l,int r,int id) {
	int mid=(L+R)/2;
	if(L==l&&R==r) return sum[id];
	else if(r<=mid) return query(L,mid,l,r,id*2);
	else if(l> mid) return query(mid+1,R,l,r,id*2+1);
	else return query(L,mid,l,mid,id*2)*query(mid+1,R,mid+1,r,id*2+1);
}
int gans(MM x,int h) {
	return max(max(x.a[1][h],x.a[2][h]),x.a[3][h]);
} 
void build(int id,int L,int R) {
	if(L==R) {
		sum[id].a[1][1]=0,sum[id].a[1][2]=-inf,sum[id].a[1][3]=-inf;
		sum[id].a[2][1]=s[L],sum[id].a[2][2]=s[L],sum[id].a[2][3]=-inf;
		sum[id].a[3][1]=0,sum[id].a[3][2]=0,sum[id].a[3][3]=0;
		return;
	}
	int mid=(L+R)/2;
	build(id*2,L,mid);
	build(id*2+1,mid+1,R);
	sum[id]=sum[id*2]*sum[id*2+1];
}
signed main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&s[i]);
    build(1,1,n);
    scanf("%d",&m);
    while(m--) {
    	int opt,xx,yy;
    	scanf("%d%d%d",&opt,&xx,&yy);
    	if(opt==0) xg(1,n,xx,yy,1);
    	else {
    		//printf("%d %d %d\n",sum[1].a[1][3],sum[1].a[2][3],sum[1].a[3][3]);
    		printf("%d\n",gans(query(1,n,xx,yy,1),1));
		}
	}
    return 0;
}