#include <bits/stdc++.h>
#define int long long
using namespace std;
template <typename T>
string to_string (T x) {
string S = "[";
bool first = true;
for (const auto v : x) {
if (!first) S += ", ";
first = false;
S += to_string(v);
}
S += "]";
return S;
}
string to_string (string S) { return S; }
template <typename A, typename B>
string to_string (pair<A, B> p) {
return "(" + to_string(p.first )+ ", " + to_string(p.second) + ")";
}
void dbg_out () { cout << endl; }
template <typename Head, typename... Tail>
void dbg_out (Head H, Tail... T) {
cout << to_string(H) << " ";
dbg_out(T...);
}
#ifdef DEBUG
# define dbg(...) { cout << "(" << #__VA_ARGS__ << "): "; dbg_out(__VA_ARGS__); }
#else
# define dbg(...)
#endif
using idata = vector<int>;
using igrid = vector<idata>;
template<typename T>
using grid = vector<vector<T>>;
using di = pair<int, int>; using vd = vector<di>;
using ti = pair<di, int> ; using vt = vector<ti>;
igrid opt;
struct Monoid {
int p = 0, q = 0, ppq = 0;
Monoid () = default;
Monoid (int p, int q, int ppq) : p(p), q(q), ppq(ppq) {}
static Monoid merge (Monoid &left, Monoid &right) {
return Monoid( max(left.p, right.p), max(left.q, right.q), max(left.p + right.q, max(left.ppq, right.ppq)) );
}
};
struct SegTree {
vector<Monoid> tree;
int start, height, size;
SegTree (int _size) {
size = _size;
height = ceil(log2(size));
start = 1 << height;
tree.resize(start << 1);
}
void update (int i) {
i += start;
i >>= 1;
while (i != 0) {
tree[i] = Monoid::merge(tree[2 * i], tree[2 * i + 1]);
i >>= 1;
}
}
void modify_p (int i, int p) {
tree[i + start].p = max(tree[i + start].p, p);
tree[i + start].ppq = max(tree[i + start].ppq, tree[i + start].p + tree[i + start].q);
update(i);
}
void modify_q (int i, int q) {
tree[i + start].q = max(tree[i + start].q, q);
tree[i + start].ppq = max(tree[i + start].ppq, tree[i + start].p + tree[i + start].q);
update(i);
}
int query (int l, int r) {
l += start; r += start;
Monoid resL;
Monoid resR;
idata qL, qR;
while (l < r) {
if ((l & 1) == 1) resL = Monoid::merge(resL, tree[l]);
if ((r & 1) == 0) resR = Monoid::merge(tree[r], resR);
l = (l + 1) >> 1;
r = (r - 1) >> 1;
}
if (l == r) resL = Monoid::merge(resL, tree[l]);
return Monoid::merge(resL, resR).ppq;
}
};
signed main () {
int N;
cin >> N;
idata A(N);
for (int i = 0; i < N; i ++)
cin >> A[i];
opt.resize(N);
deque<int> local;
for (int i = 0; i < N; i ++) {
while (local.size() != 0 && A[local.front()] < A[i]) {
int curr = local.front(); local.pop_front();
opt[i].push_back(curr);
}
if (local.size() != 0) opt[i].push_back(local.front());
local.push_front(i);
}
vd opt_q;
for (int i = 0; i < N; i ++) {
for (int a : opt[i]) {
opt_q.push_back({ a, i });
}
}
sort(opt_q.begin(), opt_q.end());
reverse(opt_q.begin(), opt_q.end());
int Q;
cin >> Q;
idata answer(Q);
vt queries;
for (int q = 0; q < Q; q ++) {
int l, r;
cin >> l >> r;
l --; r --;
queries.push_back({ { l, r }, q });
}
sort(queries.begin(), queries.end());
reverse(queries.begin(), queries.end());
int opt_q_id = 0;
int query_id = 0;
SegTree tree(N);
for (int i = 0; i < N; i ++)
tree.modify_q(i, A[i]);
for (int i = N - 1; i >= 0; i --) {
while (opt_q_id != opt_q.size() && opt_q[opt_q_id].first == i) {
int optA = opt_q[opt_q_id].first;
int optB = opt_q[opt_q_id].second;
opt_q_id ++;
int optC = 2 * optB - optA;
if (optC > N) continue ;
tree.modify_p(optC, A[optA] + A[optB]);
}
while (query_id != queries.size() && queries[query_id].first.first == i) {
int l = queries[query_id].first.first;
int r = queries[query_id].first.second;
int i = queries[query_id].second;
query_id ++;
answer[i] = tree.query(l, r);
}
}
for (int u : answer) cout << u << "\n";
}
