#include<bits/stdc++.h>
#define pt putchar
using namespace std;
typedef long long ll;
int read();void write(int);
const int N=5e5+5;
int n,a[N],q;
int ld[N];
int st[N],top;
vector<int>J[N],Q[N];
int r[N];//query,also ans

namespace SGT{
	int mxa[N*4],mxb[N*4],ans[N*4];
	#define se int k,int l,int r
	#define lc k<<1,l,(l+r)>>1
	#define rc k<<1|1,((l+r)>>1)+1,r
	void build(se){
		if(l==r){
			ans[k]=mxa[k]=a[l];
			return;
		}
		build(lc);build(rc);
		mxa[k]=max(mxa[k<<1],mxa[k<<1|1]);
		ans[k]=max(ans[k<<1],ans[k<<1|1]);
	}
	void md(se,int x,int y,int v){
		if(y<l||r<x)return;
		if(x<=l&&r<=y){
			mxb[k]=max(mxb[k],v);
			ans[k]=max(ans[k],mxb[k]+mxa[k]);
			return;
		}
		md(lc,x,y,v);md(rc,x,y,v);
		ans[k]=max(mxb[k]+mxa[k],max(ans[k<<1],ans[k<<1|1]));
	}
	int qu(se,int x,int y,int&ma){
		if(y<l||r<x)return 0;
		if(x<=l&&r<=y){
			ma=max(ma,mxa[k]);
			return ans[k];
		}
		int d=0,pre=max(qu(lc,x,y,d),qu(rc,x,y,d));
		ma=max(ma,d);
		return max(d+mxb[k],pre);
	} 
}

void add(int i,int j){
	if(1<=i&&j<=n&&j*2-i<=n){
		J[i].push_back(j);
		//printf("%d %d added\n",i,j);
	}
}
int main(){
	n=read();
	a[0]=a[n+1]=2e8;
	for(int i=1;i<=n;i++){
		a[i]=read();
		while(top&&a[st[top]]<=a[i])top--;
		ld[i]=st[top];
		st[++top]=i;
	}
	st[top=0]=n+1;
	for(int i=n;i>=1;i--){
		while(top&&a[st[top]]<=a[i])top--;
		add(ld[i],st[top]);
		add(i-1,i);
		st[++top]=i;
	}
	q=read();
	for(int i=1;i<=q;i++){
		int l=read();r[i]=read();
		Q[l].push_back(i);
	}
	SGT::build(1,1,n);
	for(int l=n-2;l>=1;l--){
		//printf("now:%d\n",l);
		for(int j:J[l]){
			//if(l==3)printf("l:%d %d\n",SGT::ans[3],SGT::ans[7]);
			SGT::md(1,1,n,j*2-l,n,a[l]+a[j]);
			//printf("mx %d %d %d\n",j*2-l,n,a[l]+a[j]);
			//if(l==3)printf("l:%d %d\n",SGT::ans[3],SGT::ans[7]);
		}
		//if(l==2)printf("ans:%d\n",SGT::ans[7]);
		for(int j:Q[l]){
			int o=0;
			//printf("qu %d:%d %d\n",j,1,r[j]);
			r[j]=SGT::qu(1,1,n,l,r[j],o);
		}
	}
	for(int i=1;i<=q;i++){
		write(r[i]),pt('\n');
	}
	return 0;
}
/*
15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
1
11 14
*/
int read(){
	int x=0,f=1;
	char c='A';
	while(c<'0'||c>'9'){
		c=getchar();
		if(c=='-')f=-f;
	}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
void write(int x){
	if(x<0){
		pt('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	pt(x%10+'0');
}