///
/// Oh? You're approaching me?
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
const int N = 500010;
const int inf = 5e8;
int arr[N];
int n, q;
namespace seg{
int lzy[N<<2], mx[N<<2], mxc[N<<2];
void tag(int i, int x){
mx[i] = max(mx[i], mxc[i]+x);
lzy[i] = max(lzy[i], x);
}
void ppg(int i){
if(lzy[i]>-inf){
tag(2*i+1, lzy[i]);
tag(2*i+2, lzy[i]);
lzy[i]=-inf;
}
}
void init(int i=0, int b=0, int e=n){
lzy[i]=-inf; mx[i]=-inf;
if(e-b==1) {mxc[i] = arr[b]; return;}
init(2*i+1,b,(b+e)/2);
init(2*i+2,(b+e)/2,e);
mxc[i] = max(mxc[2*i+1], mxc[2*i+2]);
}
void up(int l, int r, int x, int i=0, int b=0, int e=n){
if(l<=b&&e<=r) return tag(i, x);
if(r<=b||e<=l) return;
ppg(i);
up(l,r,x,2*i+1,b,(b+e)/2);
up(l,r,x,2*i+2,(b+e)/2,e);
mx[i] = max(mx[2*i+1], mx[2*i+2]);
}
int get(int l, int r, int i=0, int b=0, int e=n){
if(l<=b&&e<=r) return mx[i];
if(r<=b||e<=l) return -inf;
ppg(i);
return max(
get(l,r,2*i+1,b,(b+e)/2),
get(l,r,2*i+2,(b+e)/2,e)
);
}
}
//namespace seg{
// int mx[N];
// void init(){
// Loop(i,0,N) mx[i] = -inf;
// }
// int get(int l, int r){
// int ans=0;
// Loop(i,l,r) ans = max(ans,mx[i]);
// return ans;
// }
// void up(int l, int r, int x){
// Loop(i,l,r) mx[i] = max(mx[i],x+arr[i]);
// }
//}
vector<pii> ql[N];
vector<int> cand[N];
int ans[N];
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n;
Loop(i,0,n) cin >> arr[i];
seg::init();
vector<int> st;
Loop(i,0,n){
while(st.size() && arr[st.back()] < arr[i])
st.pop_back();
if(st.size())
cand[st.back()].push_back(i);
st.push_back(i);
}
st.clear();
LoopR(i,0,n){
while(st.size() && arr[st.back()] < arr[i])
st.pop_back();
if(st.size())
cand[i].push_back(st.back());
st.push_back(i);
}
cin >> q;
Loop(i,0,q){
int l, r;
cin >> l >> r; --l;
ql[l].push_back({i,r});
}
LoopR(i,0,n){
for(int j : cand[i]){
// cout << i << ' ' << j << '\n';
if(2*j-i<n) seg::up(2*j-i,n,arr[i]+arr[j]);
}
for(auto [j, r] : ql[i]){
ans[j] = seg::get(i,r);
}
}
Loop(i,0,q) cout << ans[i] << '\n';
}
