#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 19;
struct Node{
int a, b, v;
Node(){ a = b = v = 0; }
Node(int a, int b, int v) : a(a), b(b), v(v) {}
friend Node operator + (const Node &l, const Node &r){
return { max(l.a, r.a), max(l.b, r.b), max({ l.v, r.v, l.a + r.b }) };
}
} T[SZ << 1];
int N, Q, A[SZ], R[SZ];
vector<pair<int,int>> Upd[SZ], Qry[SZ];
void Init(){
for(int i=0; i<SZ; i++) T[i|SZ].b = T[i|SZ].v = A[i];
for(int i=SZ-1; i; i--) T[i] = T[i<<1] + T[i<<1|1];
}
void Update(int x, int v){
x |= SZ;
T[x].a = max(T[x].a, v);
T[x].v = T[x].a + T[x].b;
while(x >>= 1) T[x] = T[x<<1] + T[x<<1|1];
}
int Query(int l, int r){
Node lv, rv; l |= SZ; r |= SZ;
while(l <= r){
if(l & 1) lv = lv + T[l++];
if(~r & 1) rv = T[r--] + rv;
l >>= 1; r >>= 1;
}
return (lv + rv).v;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> N;
for(int i=1; i<=N; i++) cin >> A[i];
cin >> Q;
for(int i=1,l,r; i<=Q; i++) cin >> l >> r, Qry[l].emplace_back(r, i);
Init();
stack<int> S;
for(int i=1; i<=N; i++){
while(!S.empty()){
int j = S.top();
Upd[j].emplace_back(i, A[i] + A[j]);
if(A[i] <= A[j]) break;
S.pop();
}
S.push(i);
}
for(int i=N; i>=1; i--){
for(auto [idx,val] : Upd[i]) if(2*idx - i <= N) Update(2*idx - i, val);
for(auto [end,idx] : Qry[i]) R[idx] = Query(i, end);
}
for(int i=1; i<=Q; i++) cout << R[i] << "\n";
}
