#include <iostream>
using namespace std;
const int N=1e5+7, K=27;
const int oo=1e9;
int n, m;
int a[N];
struct node{
	int dp[4][K];
}tree[N];
node pushup(node x, node y){
	node ans;
	for(int i=0;i<=3;i++)
		for(int j=0;j<=20;j++)
			ans.dp[i][j]=-oo;
	for(int i=0;i<=20;i++)
		for(int j=0;j<=20;j++){
			if(i+j<=20){
				ans.dp[0][i+j]=max(max(max(ans.dp[0][i+j], x.dp[0][i]+y.dp[0][j]), x.dp[2][i]+y.dp[0][j]), x.dp[0][i]+y.dp[1][j]);
				ans.dp[1][i+j]=max(max(max(ans.dp[1][i+j], x.dp[1][i]+y.dp[0][j]), x.dp[3][i]+y.dp[0][j]), x.dp[3][i]+y.dp[1][j]);
				ans.dp[2][i+j]=max(max(max(ans.dp[2][i+j], x.dp[0][i]+y.dp[2][j]), x.dp[2][i]+y.dp[2][j]), x.dp[0][i]+y.dp[3][j]);
				ans.dp[3][i+j]=max(max(max(ans.dp[3][i+j], x.dp[1][i]+y.dp[2][j]), x.dp[3][i]+y.dp[2][j]), x.dp[1][i]+y.dp[3][j]);
			}
			if(i+j<=21){
				ans.dp[0][i+j-1]=max(x.dp[2][i]+y.dp[1][j], ans.dp[0][i+j-1]);
				ans.dp[1][i+j-1]=max(ans.dp[1][i+j-1], x.dp[3][i]+y.dp[1][j]);
				ans.dp[2][i+j-1]=max(ans.dp[2][i+j-1], x.dp[2][i]+y.dp[3][j]);
				ans.dp[3][i+j-1]=max(ans.dp[3][i+j-1], x.dp[3][i]+y.dp[3][j]);
			}
		}
	return ans;
}
void init(int x, int val){
	tree[x].dp[0][0]=0;
	tree[x].dp[3][1]=val;
	for(int i=0;i<=3;i++)
		for(int j=0;j<=n;j++)
			if(!(i==0 && j==0) && !(i==3 && j==1))
				tree[x].dp[i][j]=-oo;
}
void build(int x, int l, int r){
	if(l==r){
		init(x, a[l]);
	}else{
		int mid=(l+r)>>1;
		build(x<<1, l, mid);
		build(x<<1|1, mid+1, r);
		tree[x]=pushup(tree[x<<1], tree[x<<1|1]);
	}
}
void update(int x, int l, int r, int were, int val){
	if(l==r){
		init(x, val);
	}else{
		int mid=(l+r)>>1;
		if(were<=mid)
			update(x<<1, l, mid, were, val);
		else
			update(x<<1|1, mid+1, r, were, val);
		tree[x]=pushup(tree[x<<1], tree[x<<1|1]);
	}
}
node query(int x, int l, int r, int L, int R){
	if(L<=l && r<=R){
		return tree[x];
	}else{
		int mid=(l+r)>>1;
		if(R<=mid)
			return query(x<<1, l, mid, L, R);
		else if(L>mid)
			return query(x<<1|1, mid+1, r, L, R);
		else{
			node s1=query(x<<1, l, mid, L, R);
			node s2=query(x<<1|1, mid+1, r, L, R);
			return pushup(s1, s2);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1, 1, n);
	cin>>m;
	while(m--){
		int c;
		cin>>c;
		if(c==0){
			int were, val;
			cin>>were>>val;
			update(1, 1, n, were, val);
		}else{
			int l, r, k;
			cin>>l>>r>>k;
			node tmp=query(1, 1, n, l, r);
			int ans=0;
			for(int i=0;i<=k;i++)
				for(int j=0;j<=3;j++)
					ans=max(ans, tmp.dp[j][i]);
			cout<<ans<<endl;
		}
	}
	return 0;
}

WA