#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5, inf = 1e9;
vector<pair<int, int>> cands[maxn], queries[maxn];
struct SegTree {
int n, N;
vector<int> bestP, sum, lazy;
SegTree() {}
SegTree(int _n) {
n = _n, N = 1;
while (N < n) {
N <<= 1;
}
bestP.resize(2 * N, -inf);
sum.resize(2 * N, -inf);
lazy.resize(2 * N, -inf);
}
void push(int v) {
sum[v] = max(sum[v], bestP[v] + lazy[v]);
if (v < N) {
lazy[2 * v] = max(lazy[2 * v], lazy[v]);
lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
}
lazy[v] = -inf;
}
void insertP(int v, int tl, int tr, int i, int x) {
if (lazy[v] != -inf) {
push(v);
}
if (tl > i || tr <= i) {
return;
}
if (tl + 1 == tr) {
bestP[v] = max(bestP[v], x);
return;
}
int m = tl + (tr - tl) / 2;
insertP(2 * v, tl, m, i, x);
insertP(2 * v + 1, m, tr, i, x);
bestP[v] = max(bestP[2 * v], bestP[2 * v + 1]);
}
void insertP(int i, int x) {
insertP(1, 0, N, i, x);
}
void maxEq(int v, int tl, int tr, int l, int r, int x) {
if (lazy[v] != -inf) {
push(v);
}
if (tl >= r || tr <= l) {
return;
}
if (l <= tl && tr <= r) {
lazy[v] = x;
push(v);
return;
}
int m = tl + (tr - tl) / 2;
maxEq(2 * v, tl, m, l, r, x);
maxEq(2 * v + 1, m, tr, l, r, x);
sum[v] = max(sum[2 * v], sum[2 * v + 1]);
}
void maxEq(int l, int r, int x) {
maxEq(1, 0, N, l, r, x);
}
int getMax(int v, int tl, int tr, int l, int r) {
if (lazy[v] != -inf) {
push(v);
}
if (tl >= r || tr <= l) {
return -inf;
}
if (l <= tl && tr <= r) {
return sum[v];
}
int m = tl + (tr - tl) / 2;
return max(getMax(2 * v, tl, m, l, r), getMax(2 * v + 1, m, tr, l, r));
}
int getMax(int l, int r) {
return getMax(1, 0, N, l, r);
}
~SegTree() {}
};
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> leftGreq(n, -1), rightGreq(n, n), stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && a[stk.back()] < a[i]) {
stk.pop_back();
}
if (!stk.empty()) {
leftGreq[i] = stk.back();
}
stk.emplace_back(i);
}
stk.clear();
for (int i = n - 1; i >= 0; --i) {
while (!stk.empty() && a[stk.back()] < a[i]) {
stk.pop_back();
}
if (!stk.empty()) {
rightGreq[i] = stk.back();
}
stk.emplace_back(i);
}
stk.clear();
for (int i = 0; i < n; ++i) {
if (rightGreq[i] != n && rightGreq[i] - i + rightGreq[i] < n) {
cands[2 * rightGreq[i] - i].emplace_back(i, rightGreq[i]);
}
}
for (int j = n - 1; j >= 0; --j) {
if (leftGreq[j] != -1 && j - leftGreq[j] + j < n) {
cands[2 * j - leftGreq[j]].emplace_back(leftGreq[j], j);
}
}
int q;
cin >> q;
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
--l, --r;
queries[r].emplace_back(l, i);
}
SegTree st(n);
for (int r = 0; r < n; ++r) {
while (!cands[r].empty()) {
auto [i, j] = cands[r].back();
cands[r].pop_back();
st.insertP(i, a[i] + a[j]);
}
st.maxEq(0, r, a[r]);
while (!queries[r].empty()) {
auto [l, i] = queries[r].back();
queries[r].pop_back();
ans[i] = st.getMax(l, r);
}
}
for (const int& x : ans) {
cout << x << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
