#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct node
{
ll am,bm,sm;
node(ll x=-INF,ll y=-INF):am(x),bm(y),sm(x+y){}
node(ll x,ll y,ll z):am(x),bm(y),sm(z){}
node operator^(node x)
{
return node(max(am,x.am),max(bm,x.bm),max({sm,x.sm,bm+x.am}));
}
};
ll a[500010],b[500010];
struct seg
{
node t[2000010];
void si(int n,int s,int e,int x)
{
if(s==e)
{
t[n]=node(a[s],b[s]);
return;
}
int m=s+e>>1;
if(x>m)
si(n*2+1,m+1,e,x);
else
si(n*2,s,m,x);
t[n]=t[n*2]^t[n*2+1];
return;
}
node sq(int n,int s,int e,int S,int E)
{
if(s>E||S>e)
return node();
if(S<=s&&e<=E)
return t[n];
int m=s+e>>1;
return sq(n*2,s,m,S,E)^sq(n*2+1,m+1,e,S,E);
}
}st;
vector<pl>qv[500010];
vector<pi>av[500010];
ll ans[500010];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n;
for(int i=0;i++<n;)
cin>>a[i],b[i]=-INF;
vector<int>v;
v.eb(n);
for(int i=n;--i>0;)
{
while(!v.empty())
{
int j=v.back();
if(2*j-i<=n)
qv[i].eb(2*j-i,a[i]+a[j]);
if(a[j]<=a[i])
v.pop_back();
else
break;
}
v.eb(i);
}
cin>>q;
for(int i=0;i<q;i++)
{
int l,r;
cin>>l>>r;
av[l].eb(r,i);
}
for(int i=n;i>0;i--)
{
for(pl&t:qv[i])
if(b[t.fi]<t.se)
b[t.fi]=t.se,st.si(1,1,n,t.fi);
for(pi&t:av[i])
ans[t.se]=st.sq(1,1,n,i+2,t.fi).sm;
}
for(int i=0;i<q;i++)
cout<<ans[i]<<'\n';
cout.flush();
return 0;
}
