#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 500500;
int t[4 * N];
int mx[4 * N];
int d[4 * N];
void apply(int v, int val) {
d[v] = max(d[v], val);
t[v] = max(t[v], mx[v] + val);
}
void push(int v) {
apply(2 * v, d[v]);
apply(2 * v + 1, d[v]);
}
void upd(int v, int l, int r, int L, int R, int val) {
if (l >= R || r <= L) {
return;
}
if (l >= L && r <= R) {
apply(v, val);
return;
}
push(v);
int m = (l + r) / 2;
upd(2 * v, l, m, L, R, val);
upd(2 * v + 1, m, r, L, R, val);
t[v] = max({mx[v] + d[v], t[2 * v], t[2 * v + 1]});
}
int get(int v, int l, int r, int L, int R) {
if (l >= R || r <= L) {
return (int) -1e9;
}
if (l >= L && r <= R) {
return t[v];
}
push(v);
int m = (l + r) / 2;
return max(get(2 * v, l, m, L, R), get(2 * v + 1, m, r, L, R));
}
void build(int v, int l, int r, int a[N]) {
if (r - l == 1) {
t[v] = -1e9;
mx[v] = a[l];
d[v] = -1e9;
} else {
int m = (l + r) / 2;
build(2 * v, l, m, a);
build(2 * v + 1, m, r, a);
mx[v] = max(mx[2 * v], mx[2 * v + 1]);
d[v] = -1e9;
t[v] = -1e9;
}
}
int n;
int a[N];
vector<pair<int, int>> qr[N];
vector<int> e[N];
int q;
int ans[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
cin >> q;
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
--l;
qr[l].push_back({r, i});
}
vector<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.back()] <= a[i]) {
e[st.back()].push_back(i);
st.pop_back();
}
if (!st.empty()) {
e[st.back()].push_back(i);
}
st.push_back(i);
}
build(1, 0, n, a);
for (int i = n - 1; i >= 0; --i) {
for (int j : e[i]) {
upd(1, 0, n, i + (j - i) * 2, n, a[i] + a[j]);
}
for (auto qq : qr[i]) {
ans[qq.second] = get(1, 0, n, i, qq.first);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << "\n";
}
}
