#include <bits/stdc++.h>
#define MN 500071
using namespace std;
int n, q, A[MN];
vector<pair<int, int> > OG;
struct nod {
int delta, origm, lazy_d;
int val, ma;
};
nod V[4 * MN];
void init(int u = 1, int s = 1, int d = n) {
if(s != d) {
init(u << 1, s, (s + d) >> 1);
init(u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u].origm = V[u].ma = V[u].val = max(V[u << 1].origm, V[u << 1 | 1].origm);
} else {
V[u].origm = V[u].val = V[u].ma = A[s];
}
}
void prop(int u, int s, int d) {
if(V[u].delta < V[u].lazy_d) {
V[u].delta = V[u].lazy_d;
V[u].val = V[u].delta + V[u].origm;
V[u].ma = max({V[u].ma, V[u].val});
}
if(s != d) {
V[u << 1].lazy_d = max(V[u << 1].lazy_d, V[u].lazy_d);
V[u << 1 | 1].lazy_d = max(V[u << 1 | 1].lazy_d, V[u].lazy_d);
}
V[u].lazy_d = 0;
}
void update(int val, int l, int r, int u = 1, int s = 1, int d = n) {
prop(u, s, d);
if(d < l || r < s) return;
if(l <= s && d <= r) {
V[u].lazy_d = val;
prop(u, s, d);
return;
}
update(val, l, r, u << 1, s, (s + d) >> 1);
update(val, l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u].ma = max({V[u].val, V[u].ma, V[u << 1].ma, V[u << 1 | 1].ma});
}
int query(int l, int r, int u = 1, int s = 1, int d = n) {
if(d < l || r < s) return 0;
prop(u, s, d);
if(l <= s && d <= r) return V[u].ma;
return max(query(l, r, u << 1, s, (s + d) >> 1), query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d));
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> A[i];
stack<int> S;
init();
for(int i = 1; i <= n; ++i) {
while(!S.empty() && A[i] > A[S.top()]) {
OG.push_back({S.top(), i});
S.pop();
}
if(!S.empty()) OG.push_back({S.top(), i});
S.push(i);
}
cin >> q;
vector<tuple<int, int, int> > Q;
for(int i = 1, st, dr; i <= q; ++i)
cin >> st >> dr, Q.push_back({st, dr, i});
vector<int> R(q + 1);
sort(Q.rbegin(), Q.rend());
sort(OG.rbegin(), OG.rend());
auto it = OG.begin();
for(auto [l, r, id] : Q) {
while(it != OG.end() && it->first >= l) {
update(A[it->first] + A[it->second], it->second * 2 - it->first, n);
//printf("Update de valoare %d de la %d la n\n", A[it->first] + A[it->second], it->second * 2 - it->first);
++it;
}
R[id] = query(l, r);
}
for(int i = 1; i <= q; ++i) cout << R[i] << "\n";
return 0;
}
