#include <bits/stdc++.h>
using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
template <class T>
using Vec = std::vector<T>;
constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
usize N;
std::cin >> N;
Vec<u32> A(N);
for (auto &x: A) {
std::cin >> x;
}
usize Q;
std::cin >> Q;
if (Q <= 20) {
while (Q--) {
usize L, R;
std::cin >> L >> R;
L -= 1;
R -= 1;
std::stack<std::pair<u32, usize>> stack;
Vec<u32> accum(N);
accum[R] = A[R];
for (usize i = R; i --> L;) {
accum[i] = std::max(A[i], accum[i + 1]);
}
u32 ans = 0;
for (usize m = L; m < R; ++m) {
while (!stack.empty()) {
const auto [v, i] = stack.top();
if (m + m - i <= R) {
ans = std::max(ans, v + A[m] + accum[m + m - i]);
}
if (v > A[m]) {
break;
}
stack.pop();
}
stack.emplace(A[m], m);
}
std::cout << ans << '\n';
}
}
else if (N <= 5000) {
Vec<Vec<u32>> dp(N, Vec<u32>(N, 0));
for (usize l = 0; l < N; ++l) {
u32 m = 0;
for (usize r = l + 2; r < N; ++r) {
m = std::max(m, A[(l + r) / 2]);
dp[l][r] = A[l] + m + A[r];
}
}
for (usize len = 2; len < N; ++len) {
for (usize l = 0; l + len < N; ++l) {
dp[l][l + len] = std::max({ dp[l][l + len], dp[l + 1][l + len], dp[l][l + len - 1] });
}
}
while (Q--) {
usize l, r;
std::cin >> l >> r;
l -= 1;
r -= 1;
std::cout << dp[l][r] << '\n';
}
}
return 0;
}
