#include <bits/stdc++.h>
using namespace std;
#define M 524288
int st[M << 1], A[M << 1], B[M << 1], C[M << 1], lz[M << 1];
// MIN MAX
void push(int x, int l, int r) {
if(lz[x] > 0) {
st[x] = A[x] + lz[x];
B[x] = C[x] = lz[x];
if(l != r) {
lz[x << 1] = lz[x << 1 | 1] = lz[x];
}
lz[x] = 0;
}
}
void update(int x, int l, int r, int ql, int qr, int d) {
push(x, l, r);
if(r < ql || qr < l || B[x] >= d) {
return;
}
if(ql <= l && r <= qr && C[x] <= d) {
lz[x] = d;
push(x, l, r);
}
else {
int m = (l + r) >> 1;
update(x << 1, l, m, ql, qr, d);
update(x << 1 | 1, m + 1, r, ql, qr, d);
st[x] = max(st[x << 1], st[x << 1 | 1]);
B[x] = min(B[x << 1], B[x << 1 | 1]);
C[x] = max(C[x << 1], C[x << 1 | 1]);
}
}
int query(int x, int l, int r, int ql, int qr) {
push(x, l, r);
if(r < ql || qr < l) {
return 0;
}
if(ql <= l && r <= qr) {
return st[x];
}
int m = (l + r) >> 1;
return max(query(x << 1, l, m, ql, qr), query(x << 1 | 1, m + 1, r, ql, qr));
}
#define N 500005
int a[N], L[N], R[N], res[N];
vector<int> pot[N];
vector<pair<int, int>> queries[N];
void build(int x, int l, int r) {
st[x] = B[x] = C[x] = 0;
if(l == r) {
A[x] = a[l];
}
else {
int m = (l + r) >> 1;
build(x << 1, l, m);
build(x << 1 | 1, m + 1, r);
A[x] = max(A[x << 1], A[x << 1 | 1]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
for(int i = 1, j; i <= n; ++i) {
j = i - 1;
while(j > 0 && a[i] > a[j]) {
j = L[j];
}
L[i] = j;
}
for(int i = n, j; i > 0; --i) {
j = i + 1;
while(j <= n && a[i] > a[j]) {
j = R[j];
}
R[i] = j;
}
for(int i = 1; i <= n; ++i) {
if(L[i] > 0) {
pot[L[i]].push_back(i);
}
if(R[i] <= n) {
pot[i].push_back(R[i]);
}
}
int q;
cin >> q;
for(int i = 1; i <= q; ++i) {
int l, r;
cin >> l >> r;
queries[l].emplace_back(i, r);
}
build(1, 1, n);
for(int i = n; i > 0; --i) {
sort(pot[i].begin(), pot[i].end());
pot[i].erase(unique(pot[i].begin(), pot[i].end()), pot[i].end());
for(int j : pot[i]) {
int k_min = j + j - i;
if(k_min <= n) {
update(1, 1, n, k_min, n, a[i] + a[j]);
}
}
for(const auto& [j, r] : queries[i]) {
res[j] = query(1, 1, n, i, r);
}
}
for(int i = 1; i <= q; ++i) {
cout << res[i] << '\n';
}
return 0;
}
