#include <bits/stdc++.h>
using namespace std;
const long long MX=5e5+10,INF=1e9;
long long a[MX],ans[MX];
vector < pair < long long , long long > > goodpairs;
long long n;
struct nd
{
long long mxa;
long long mxc;
long long mxabc;
} tree[4*MX];
void smlupd(long long v,long long zn)
{
tree[v].mxa=max(tree[v].mxa,zn);
tree[v].mxabc=max(tree[v].mxabc,tree[v].mxc+tree[v].mxa);
}
long long fget(long long v,long long tl,long long tr,long long l,long long r)
{
if(tr<l || r<tl){
return 0;
}
if(l<=tl && tr<=r){
return tree[v].mxabc;
}
smlupd(v*2,tree[v].mxa);
smlupd(v*2+1,tree[v].mxa);
long long mid=(tl+tr)/2;
return max(fget(v*2,tl,mid,l,r),fget(v*2+1,mid+1,tr,l,r));
}
long long clc(pair < long long , long long > zp)
{
return fget(1,1,n,zp.first,zp.second);
}
void build(long long v,long long tl,long long tr)
{
if(tl==tr){
tree[v].mxc=a[tl];
return;
}
long long mid=(tl+tr)/2;
build(v*2,tl,mid);
build(v*2+1,mid+1,tr);
tree[v].mxc=max(tree[v*2].mxc,tree[v*2+1].mxc);
}
void upd(long long v,long long tl,long long tr,long long l,long long r,long long zn)
{
if(r<tl || tr<l){
return;
}
if(l<=tl && tr<=r){
smlupd(v,zn);
return;
}
smlupd(v*2,tree[v].mxa);
smlupd(v*2+1,tree[v].mxa);
long long mid=(tl+tr)/2;
upd(v*2,tl,mid,l,r,zn);
upd(v*2+1,mid+1,tr,l,r,zn);
tree[v].mxabc=max(tree[v*2].mxabc,tree[v*2+1].mxabc);
}
void fad(pair < long long , long long > pr)
{
long long va=pr.first;
long long vb=pr.second;
if(2*vb-va<=n)
{
upd(1,1,n,2*vb-va,n,a[va]+a[vb]);
}
}
void clcgoodpair()
{
stack < pair < long long , long long > > st;
st.push({INF,0});
for(long long i=1;i<=n;i++){
while(st.top().first<a[i]){
st.pop();
}
if(st.top().second!=0){
goodpairs.push_back({st.top().second,i});
}
st.push({a[i],i});
}
while(!st.empty()){
st.pop();
}
st.push({INF,n+1});
for(long long i=n;i>=1;i--){
while(st.top().first<=a[i]){
st.pop();
}
if(st.top().second!=n+1){
goodpairs.push_back({i,st.top().second});
}
st.push({a[i],i});
}
}
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
clcgoodpair();
vector < pair < pair < long long , long long > , long long > > zap;
long long q;
cin>>q;
for(long long i=1;i<=q;i++){
long long l,r;
cin>>l>>r;
zap.push_back({{l,r},i});
}
sort(goodpairs.begin(),goodpairs.end());
reverse(goodpairs.begin(),goodpairs.end());
goodpairs.push_back({0,0});
sort(zap.begin(),zap.end());
reverse(zap.begin(),zap.end());
zap.push_back({{0,0},0});
long long ukv=0,ukz=0;
for(long long i=n;i>=1;i--){
while(goodpairs[ukv].first==i){
fad(goodpairs[ukv]);
ukv++;
}
while(zap[ukz].first.first==i){
ans[zap[ukz].second]=clc(zap[ukz].first);
ukz++;
}
}
for(long long i=1;i<=q;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
