#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=5e5+10;
int n, q, a[MAXN];
struct tree{
    int l, r;
    int sum, lmax, rmax, dat;
};
tree t[MAXN*4];

void build(int p, int l, int r)
{
    t[p].l=l, t[p].r=r;
    if(l==r)
    {
        t[p].sum=a[l]; t[p].lmax=a[l]; t[p].rmax=a[l]; t[p].dat=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(p*2, l, mid), build(p*2+1, mid+1, r);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
    t[p].lmax=max(t[p*2].lmax, t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax, t[p*2+1].sum+t[p*2].rmax);
    t[p].dat=max(t[p*2].dat, max(t[p*2+1].dat, t[p*2].rmax+t[p*2+1].lmax));
}

int qlmax(int p, int qr)
{
	int l=t[p].l, r=t[p].r, mid=(l+r)/2;
	if(qr==r) return t[p].lmax;
	if(qr<=mid) return qlmax(p*2, qr);
	return t[p*2].sum+qlmax(p*2+1, qr);
}

int qrmax(int p, int ql)
{
	int l=t[p].l, r=t[p].r, mid=(l+r)/2;
	if(ql==l) return t[p].rmax;
	if(mid+1<=ql) return qrmax(p*2+1, ql);
	return t[p*2+1].sum+qrmax(p*2, ql);
}

int query(int p, int ql, int qr)
{
	int l=t[p].l, r=t[p].r, mid=(l+r)/2;
	if(ql==l&&qr==r) return t[p].dat;
	if(l<=ql&&qr<=mid) return query(p*2, ql, qr);
	if(mid+1<=ql&&qr<=r) return query(p*2+1, ql, qr);
	return max(qrmax(p*2, ql)+qlmax(p*2+1, qr), max(query(p*2, ql, mid), query(p*2+1, mid+1, qr)));
}

void change(int p, int x, int k)
{
	int l=t[p].l, r=t[p].r, mid=(l+r)/2;
	if(l==r)
    {
        t[p].sum=k; t[p].lmax=k; t[p].rmax=k; t[p].dat=k;
        return ;
    }
	if(x<=mid) change(p*2, x, k);
	else change(p*2+1, x, k);
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
    t[p].lmax=max(t[p*2].lmax, t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax, t[p*2+1].sum+t[p*2].rmax);
    t[p].dat=max(t[p*2].dat, max(t[p*2+1].dat, t[p*2].rmax+t[p*2+1].lmax));
}

int main()
{
	scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    
	build(1, 1, n);
	
	scanf("%d", &q);
	while(q--)
	{
		int k, x, y;
		scanf("%d%d%d", &k, &x, &y);
		if(k==1) printf("%d\n", query(1, x, y));
		else change(1, x, y);
	}
	
    return 0;
}

造了些数据，都是对的，也没检查出什么错