#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000007
#define MAXN 300000
using namespace std;
int t[4*MAXN+1],lazy[4*MAXN+1],ans[4*MAXN+1];
void build(int v,int tl,int tr,int a[]){
if (tl==tr)t[v]=ans[v]=a[tl];else{
int tm=(tl+tr)/2;
build(v*2,tl,tm,a);
build(v*2+1,tm+1,tr,a);
t[v]=max(t[v*2],t[v*2+1]);
ans[v]=max(ans[v*2],ans[v*2+1]);
}
}
void push(int v){
ans[2*v]=max(ans[2*v],t[2*v]+lazy[v]);
ans[2*v+1]=max(ans[2*v+1],t[2*v+1]+lazy[v]);
lazy[2*v]=max(lazy[2*v],lazy[v]);
lazy[2*v+1]=max(lazy[2*v+1],lazy[v]);
lazy[v]=0;
}
void up(int v,int tl,int tr,int l,int r,int delta){
if (l>r)return;
if (tl==l && tr==r){
ans[v]=max(ans[v],t[v]+delta);
lazy[v]=max(lazy[v],delta);
}else{
push(v);
int tm=(tl+tr)/2;
up(v*2,tl,tm,l,min(r,tm),delta);
up(v*2+1,tm+1,tr,max(l,tm+1),r,delta);
ans[v]=max(ans[2*v],ans[2*v+1]);
}
}
int get(int v,int tl,int tr,int l,int r){
if (l>r)return 0;
if (tl==l && tr==r)return ans[v];
push(v);
int tm=(tl+tr)/2;
return max(get(v*2,tl,tm,l,min(r,tm)),get(v*2+1,tm+1,tr,max(l,tm+1),r));
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n;
cin>>n;
int a[n+1];
for (int i=1;i<=n;i++)cin>>a[i];
stack <int> s;
vvi inds(n+1);
for (int i=1;i<=n;i++){
while (!s.empty() && a[s.top()]<a[i])s.pop();
if (!s.empty()){
if (2*i-s.top()<=n)inds[s.top()].pb(i);
}
s.push(i);
inds[i].pb(i+1);
}
while(!s.empty())s.pop();
for (int i=n;i>=1;i--){
while (!s.empty() && a[s.top()]<a[i])s.pop();
if (!s.empty()){
if (2*s.top()-i<=n)inds[i].pb(s.top());
}
s.push(i);
}
build(1,1,n,a);
int q;
cin>>q;
vvp R(n+1);
for (int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
R[l].pb({r,i});
}
int res[q+1];
for (int i=n;i>=1;i--){
for (int x:inds[i])up(1,1,n,2*x-i,n,a[x]+a[i]);
for (auto &[r,id]:R[i])res[id]=get(1,1,n,i,r);
}
for (int i=1;i<=q;i++)cout<<res[i]<<'\n';
}
