#include <bits/stdc++.h>
using namespace std;
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();
vector<int> sufMax(n);
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
--l, --r;
sufMax[r] = a[r];
for (int i = r - 1; i >= l; --i) {
sufMax[i] = max(sufMax[i + 1], a[i]);
}
int ans = 0;
for (int i = l; i < r; ++i) {
if (rightGreq[i] < r && rightGreq[i] - i <= r - rightGreq[i]) {
ans = max(ans, a[i] + a[rightGreq[i]] + sufMax[rightGreq[i] + rightGreq[i] - i]);
}
}
for (int j = r - 1; j > l; --j) {
if (leftGreq[j] >= l && j - leftGreq[j] <= r - j) {
ans = max(ans, a[j] + a[leftGreq[j]] + sufMax[j + j - leftGreq[j]]);
}
}
cout << ans << '\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;
}
