#include<bits/stdc++.h>
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e5+10;
int n,q,a[MAXN],mx[MAXN<<2],ma[MAXN<<2],tag[MAXN<<2];
void build(int k,int l,int r) {
	if(l==r) return mx[k]=ma[k]=a[l],void();
	build(lson,l,mid),build(rson,mid+1,r);
	return mx[k]=max(mx[lson],mx[rson]),ma[k]=max(ma[lson],ma[rson]),void();	
}
void push_down(int k,int l,int r) {
	ma[lson]=max(ma[lson],mx[lson]+tag[k]),ma[rson]=max(ma[rson],mx[rson]+tag[k]);
	tag[lson]=max(tag[lson],tag[k]),tag[rson]=max(tag[rson],tag[k]);
	return ;	
}
void update(int k,int l,int r,int x,int y,int v) {
	if(x<=l&&r<=y) return ma[k]=max(ma[k],mx[k]+v),tag[k]=max(tag[k],v),void();
	push_down(k,l,r);
	if(x<=mid) update(lson,l,mid,x,y,v);
	if(y>mid) update(rson,mid+1,r,x,y,v);
	return ma[k]=max(ma[lson],ma[rson]),void();
}
int query(int k,int l,int r,int x,int y) {
	if(x<=l&&r<=y) return ma[k];
	push_down(k,l,r);
	if(y<=mid) return query(lson,l,mid,x,y);
	if(x>mid) return query(rson,mid+1,r,x,y);
	return max(query(lson,l,mid,x,y),query(rson,mid+1,r,x,y));	
}
int ans[MAXN];
vector<pair<int,int>> qr[MAXN];
vector<int> upd[MAXN];
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,1,n) cin>>a[i];
	build(1,1,n),cin>>q;
	ffor(i,1,q) {int l,r;cin>>l>>r,qr[l].push_back({r,i});}
	stack<int> st;
	ffor(i,1,n) {
		while(!st.empty()&&a[i]>a[st.top()]) st.pop();
		if(!st.empty()) upd[st.top()].push_back(i);
		st.push(i);
	}
	while(!st.empty()) st.pop();
	roff(i,n,1) {
		while(!st.empty()&&a[i]>a[st.top()]) st.pop();
		if(!st.empty()) upd[i].push_back(st.top());
		st.push(i);	
	}
	roff(i,n,1) {
		for(auto id:upd[i]) if(2*id-i<=n) update(1,1,n,2*id-i,n,a[i]+a[id]);
		for(auto pr:qr[i]) ans[pr.second]=max(ans[pr.second],query(1,1,n,i,pr.first));
	}
	ffor(i,1,q) cout<<ans[i]<<'\n';
	return 0;
}