#include<bits/stdc++.h>
#define int long long
const int INF=1e17;
using namespace std;
int n,m,q;
int a[500005];
struct Matrix {		
 	int wide,len;														
	long long c[4][4];
}jz[50005*4];
Matrix operator*(const Matrix &x,const Matrix &y) {							
	Matrix a;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			a.c[i][j]=-INF;
		}
	}
		
	for(int i=1; i<=3; i++)
		for(int j=1; j<=3; j++)
			for(int k=1; k<=3; k++)	
				a.c[i][j]=max(a.c[i][j],x.c[i][k]+y.c[k][j]);
			
	a.len=y.len;
	a.wide=x.wide;
	return a;
}
struct node{
	int ll;
	int rr;
}tree[500005*4];
void pushup(int rt){
	jz[rt]=jz[rt*2]*jz[rt*2+1];
}
void build(int rt ,int l,int r){
	tree[rt].ll=l;
	tree[rt].rr=r;
	int mid=(l+r)>>1;
	if(l==r){
		jz[rt].len=3;
		jz[rt].len=3;
		jz[rt].c[1][1]=a[l];
		jz[rt].c[1][2]=a[l];
		jz[rt].c[3][1]=a[l];
		jz[rt].c[3][2]=a[l];
		jz[rt].c[2][2]=0;
		jz[rt].c[3][3]=0;
		jz[rt].c[1][3]=-INF;
		jz[rt].c[2][1]=-INF;
		jz[rt].c[2][3]=-INF;
		return ;
	}
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	pushup(rt);
}
void change(int rt,int pos,int val){
	int le=tree[rt].ll;
	int ri=tree[rt].rr;
	if(pos<le||pos>ri){
		return;
	}
	if(le==ri){
		jz[rt].len=3;
		jz[rt].len=3;
		jz[rt].c[1][1]=val;
		jz[rt].c[1][2]=val;
		jz[rt].c[3][1]=val;
		jz[rt].c[3][2]=val;
		jz[rt].c[2][2]=0;
		jz[rt].c[3][3]=0;
		jz[rt].c[1][3]=-INF;
		jz[rt].c[2][1]=-INF;
		jz[rt].c[2][3]=-INF;
		
		return;
	}
	change(rt*2,pos,val);
	change(rt*2+1,pos,val);
	pushup(rt); 
}
Matrix query( int rt, int L, int R ) {
	int l=tree[rt].ll;
	int r=tree[rt].rr;
	if( L <= l && r <= R ) return jz[rt];
	int mid = ( l + r ) >> 1;
	if( R <= mid ) return query( rt*2,L, R );
	else if( mid < L ) return query( rt*2+1, L, R );
	else return query( rt*2, L, R ) * query( rt*2+1, L, R );
}

signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	build(1,1,n);
	int q;
	scanf("%lld",&q);
	while(q--){
		int op,x,y;
		scanf("%lld%lld%lld",&op,&x,&y);
		if(op==0){
			change(1,x,y);
		}
		else{
			printf("%lld\n",query(1,x,y).c[3][2]);
		}
	}
}