#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;
struct Mn {
u32 whole, value;
static Mn id() {
return Mn { 0, 0 };
}
Mn operator + (const Mn other) const {
return Mn { std::max(whole, other.whole), std::max(value, other.value) };
}
};
struct Ef {
u32 add;
static Ef id() {
return Ef { 0 };
}
Ef operator + (const Ef other) const {
return Ef { std::max(add, other.add) };
}
};
Mn operator + (const Mn mn, const Ef ef) {
return Mn { std::max(mn.whole, mn.value + ef.add), mn.value };
}
struct Segtree {
struct Node {
Mn mn;
Ef ef;
};
void fetch(const usize i) {
data[i].mn = data[i * 2 + 0].mn + data[i * 2 + 1].mn;
}
void apply(const usize i, const Ef ef) {
data[i].mn = data[i].mn + ef;
data[i].ef = data[i].ef + ef;
}
void flush(const usize i) {
apply(i * 2 + 0, data[i].ef);
apply(i * 2 + 1, data[i].ef);
}
static usize ctzr(const usize i) {
return __builtin_ctzll(i);
}
static usize height(const usize i) {
return 64 - __builtin_clzll(i);
}
void pushdown(const usize i) {
const auto lsb = ctzr(i);
for (usize d = height(i); --d > lsb;) {
flush(i >> d);
}
}
void pullup(usize i) {
i >>= ctzr(i);
while (i != 1) {
i >>= 1;
fetch(i);
}
}
std::vector<Node> data;
Segtree(const std::vector<u32> &vec) {
const auto size = vec.size();
data.resize(size * 2, Node { Mn::id(), Ef::id() });
for (usize i = 0; i < size; ++i) {
data[size + i].mn.whole = vec[i];
data[size + i].mn.value = vec[i];
}
for (usize i = size - 1; i > 0; --i) {
fetch(i);
}
}
void operate(usize l, usize r, const u32 x) {
l += size();
r += size();
pushdown(l);
pushdown(r);
const auto cl = l;
const auto cr = r;
const auto ef = Ef { x };
while (l < r) {
if (l & 1) {
apply(l, ef);
l += 1;
}
if (r & 1) {
r -= 1;
apply(r, ef);
}
l >>= 1;
r >>= 1;
}
pullup(cl);
pullup(cr);
}
u32 fold(usize l, usize r) {
l += size();
r += size();
pushdown(l);
pushdown(r);
Mn mn = Mn::id();
while (l < r) {
if (l & 1) {
mn = mn + data[l].mn;
l += 1;
}
if (r & 1) {
r -= 1;
mn = mn + data[r].mn;
}
l >>= 1;
r >>= 1;
}
return mn.whole;
}
usize size() const {
return data.size() / 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;
}
std::vector<std::vector<usize>> cand(N);
std::stack<usize> stack;
for (usize m = 0; m < N - 1; ++m) {
while (!stack.empty()) {
const auto l = stack.top();
if (m + (m - l) < N) {
cand[l].push_back(m);
}
if (A[l] > A[m]) {
break;
}
stack.pop();
}
stack.push(m);
}
usize Q;
std::cin >> Q;
std::vector<std::vector<std::pair<usize, usize>>> query(N);
for (usize i = 0; i < Q; ++i) {
usize l, r;
std::cin >> l >> r;
l -= 1;
query[l].emplace_back(i, r);
}
Segtree seg(A);
std::vector<usize> ans(Q);
for (usize l = N; l --> 0;) {
for (const auto m: cand[l]) {
const auto r = m + (m - l);
seg.operate(r, N, A[l] + A[m]);
}
for (const auto [i, r]: query[l]) {
ans[i] = seg.fold(l + 2, r);
}
}
for (const auto x: ans) {
std::cout << x << '\n';
}
return 0;
}
