#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() {
usize N;
std::cin >> N;
std::vector<u32> A(N);
for (auto &x: A) {
std::cin >> x;
}
if (N <= 5000) {
std::vector<std::vector<u32>> dp(N, std::vector<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] });
}
}
usize Q;
std::cin >> Q;
while (Q--) {
usize l, r;
std::cin >> l >> r;
l -= 1;
r -= 1;
std::cout << dp[l][r] << '\n';
}
}
return 0;
}
