#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 5e5 + 10;
int lazy[N << 2], T[N << 2], mx[N << 2];
int a[N], ans[N];
vector<pair<int, int> > query[N];
void build(int s, int l, int r) {
lazy[s] = -2e9;
if (l == r) {
mx[s] = a[l];
return;
}
int mid = l + r >> 1;
build(s << 1, l, mid);
build(s << 1 | 1, mid + 1, r);
mx[s] = max(mx[s << 1], mx[s << 1 | 1]);
}
void push(int s, int l, int r) {
T[s] = max(T[s], lazy[s] + mx[s]);
if (l != r) {
lazy[s << 1] = max(lazy[s << 1], lazy[s]);
lazy[s << 1 | 1] = max(lazy[s << 1 | 1], lazy[s]);
}
}
void up(int s, int l, int r, int from, int to, int val) {
push(s, l, r);
if (l > to || r < from) return;
if (from <= l && r <= to) {
lazy[s] = max(lazy[s], val);
push(s, l, r);
return;
}
int mid = l + r >> 1;
up(s << 1, l, mid, from, to, val);
up(s << 1 | 1, mid + 1, r, from, to, val);
T[s] = max(T[s << 1], T[s << 1 | 1]);
}
int get(int s, int l, int r, int from, int to) {
push(s, l, r);
if (l > to || r < from) return 0;
if (from <= l && r <= to) return T[s];
int mid = l + r >> 1;
return max(get(s << 1, l, mid, from, to), get(s << 1 | 1, mid + 1, r, from, to));
}
int main() {
#define task ""
cin.tie(0) -> sync_with_stdio(0);
if (fopen ("task.inp", "r")) {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
}
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
int q; cin >> q;
for(int i = 1; i <= q; i++) {
int l, r; cin >> l >> r;
query[l].emplace_back(r, i);
}
stack<int> st;
for(int i = n; i >= 1; i--) {
while (!st.empty() && a[st.top()] <= a[i]) {
up(1, 1, n, st.top() * 2 - i, n, a[st.top()] + a[i]);
st.pop();
}
if (!st.empty()) up(1, 1, n, st.top() * 2 - i, n, a[st.top()] + a[i]);
for(auto &[r, idx] : query[i]) {
ans[idx] = get(1, 1, n, i, r);
}
st.push(i);
}
for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}
