#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
using ll = long long;
using ii = pair<int, int>;
int N, Q, A[500005], ans[500005];
vector<int> ev[500005];
vector<ii> qu[500005];
stack<int> st;
struct node {
node *left, *right;
int S, E, r_val, A_val, pv;
node(int _s, int _e) : S(_s), E(_e), r_val(-(int)1e9), pv(-(int)1e9) {
if (S == E) {
A_val = A[S];
return;
}
int M = (S + E) / 2;
left = new node(S, M);
right = new node(M + 1, E);
A_val = max(left->A_val, right->A_val);
}
void prop() {
left->r_val = max(left->r_val, pv + left->A_val);
left->pv = max(left->pv, pv);
right->r_val = max(right->r_val, pv + right->A_val);
right->pv = max(right->pv, pv);
}
void upd(int l, int r, int v) {
if (l > E || r < S) {
return;
}
if (l <= S && E <= r) {
r_val = max(r_val, v + A_val);
pv = max(pv, v);
return;
}
prop();
left->upd(l, r, v);
right->upd(l, r, v);
r_val = max(left->r_val, right->r_val);
}
int qry(int l, int r) {
if (l > E || r < S) {
return -(int)1e9;
}
if (l <= S && E <= r) {
return r_val;
}
prop();
return max(left->qry(l, r), right->qry(l, r));
}
} *root;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
for (int i = N; i >= 1; i--) {
while (!st.empty() && A[st.top()] < A[i]) {
st.pop();
}
if (!st.empty()) {
ev[i].pb(st.top());
}
st.push(i);
}
while (!st.empty()) {
st.pop();
}
for (int i = 1; i <= N; i++) {
while (!st.empty() && A[st.top()] < A[i]) {
st.pop();
}
if (!st.empty()) {
ev[st.top()].pb(i);
}
st.push(i);
}
cin >> Q;
for (int i = 1, L, R; i <= Q; i++) {
cin >> L >> R;
qu[L].eb(R, i);
}
root = new node(1, N);
for (int i = N; i >= 1; i--) {
for (auto b : ev[i]) {
// a = i
root->upd(2 * b - i, N, A[i] + A[b]);
}
for (auto [r, idx] : qu[i]) {
ans[idx] = root->qry(1, r);
}
}
for (int i = 1; i <= Q; i++) {
cout << ans[i] << '\n';
}
}
