#include <bits/stdc++.h>
#define ll long long
#define MAXN 500010
using namespace std;
ll n,sz,a[MAXN],ans[MAXN];
vector<ll> p[MAXN];
vector<pair<ll,ll> > queries[MAXN];
struct element
{
ll sum,maxx;
};
element neutral={0,0};
element Merge(element x,element y)
{
return {max(x.sum,y.sum),max(x.maxx,y.maxx)};
}
struct seg_tree
{
vector<element> st;
vector<ll> lazy;
void Init()
{
sz=1;
while (sz<n)
sz <<= 1;
st.resize(2*sz+2,neutral);
lazy.resize(2*sz+2);
}
void Build()
{
for (ll i=sz;i<sz+n;i++)
st[i]={0,a[i-sz+1]};
for (ll i=sz-1;i>0;i--)
st[i]=Merge(st[2*i],st[2*i+1]);
}
void Propagate(ll x)
{
st[x].sum=max(st[x].sum,lazy[x]+st[x].maxx);
if (x<sz)
{
lazy[2*x]=max(lazy[2*x],lazy[x]);
lazy[2*x+1]=max(lazy[2*x+1],lazy[x]);
}
lazy[x]=0;
}
void Update(ll l,ll r,ll val,ll x,ll lx,ll rx)
{
Propagate(x);
if (lx>r || rx<l)
return;
if (lx>=l && rx<=r)
{
lazy[x]=val;
Propagate(x);
return;
}
ll mid=(lx+rx)/2;
Update(l,r,val,2*x,lx,mid);
Update(l,r,val,2*x+1,mid+1,rx);
st[x]=Merge(st[2*x],st[2*x+1]);
}
ll Calc(ll l,ll r,ll x,ll lx,ll rx)
{
Propagate(x);
if (lx>r || rx<l)
return 0;
if (lx>=l && rx<=r)
return st[x].sum;
ll mid=(lx+rx)/2;
return max(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
}
};
seg_tree S;
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll q,l,r;
cin >> n;
for (ll i=1;i<=n;i++)
cin >> a[i];
stack<ll> s;
for (ll i=n;i>0;i--)
{
while (!s.empty() && a[s.top()]<=a[i])
{
p[i].push_back(s.top());
s.pop();
}
if (!s.empty())
p[i].push_back(s.top());
s.push(i);
}
cin >> q;
for (ll i=1;i<=q;i++)
{
cin >> l >> r;
queries[l].push_back({r,i});
}
S.Init();
S.Build();
for (ll i=n;i>0;i--)
{
for (ll j : p[i])
{
if (2*j-i<=n)
S.Update(2*j-i,n,a[i]+a[j],1,1,sz);
}
for (auto j : queries[i])
ans[j.second]=S.Calc(i,j.first,1,1,sz);
}
for (ll i=1;i<=q;i++)
cout << ans[i] << "\n";
return 0;
}
