#include <bits/stdc++.h>
using namespace std;
#define NAME "A"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define MASK(x) (1ll << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
const int N = 5e5 + 5;
struct Node {
int l, r, id;
};
int n, q;
int a[N], ans[N];
vector<pair<int, int>> line;
vector<pair<int, int>> que[N];
struct SegmentTree {
vector<int> val, st, lazy;
SegmentTree(int n): val(n << 2 | 3), st(n << 2 | 3), lazy(n << 2 | 3) {}
void build(int l = 1, int r = n, int x = 1) {
if (l == r) {
val[x] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, x << 1);
build(mid + 1, r, x << 1 | 1);
val[x] = max(val[x << 1], val[x << 1 | 1]);
}
void down(int x) {
lazy[x << 1] = max(lazy[x << 1], lazy[x]);
lazy[x << 1 | 1] = max(lazy[x << 1 | 1], lazy[x]);
st[x << 1] = max(st[x << 1], lazy[x] + val[x << 1]);
st[x << 1 | 1] = max(st[x << 1 | 1], lazy[x] + val[x << 1 | 1]);
}
void update(int u, int v, int siu, int l = 1, int r = n, int x = 1) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
st[x] = max(st[x], siu + val[x]);
lazy[x] = max(lazy[x], siu);
return;
}
int mid = (l + r) >> 1;
down(x);
if (u <= mid) update(u, v, siu, l, mid, x << 1);
if (v > mid) update(u, v, siu, mid + 1, r, x << 1 | 1);
st[x] = max(st[x << 1], st[x << 1 | 1]);
}
int get(int u, int v, int l = 1, int r = n, int x = 1) {
if (l > v || r < u) return 0;
if (l >= u && r <= v) return st[x];
int mid = (l + r) >> 1;
down(x);
if (v <= mid) return get(u, v, l, mid, x << 1);
if (u > mid) return get(u, v, mid + 1, r, x << 1 | 1);
return max(get(u, v, l, mid, x << 1), get(u, v, mid + 1, r, x << 1 | 1));
}
};
void input() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> q;
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
que[l].pb({r, i});
}
}
void solve() {
SegmentTree st(n);
st.build();
stack<int> s;
for (int i = n; i >= 1; i--) {
while (s.size() && a[s.top()] <= a[i]) {
line.pb({i, s.top()});
s.pop();
}
if (s.size()) {
line.pb({i, s.top()});
}
s.push(i);
}
sort(all(line), greater<>());
int j = 0;
for (int i = n; i >= 1; i--) {
while (j < (int)line.size() && line[j].fi >= i) {
int l = line[j].fi, r = line[j].se;
st.update(2 * r - l, n, a[l] + a[r]);
j++;
}
for (auto it : que[i]) {
int r = it.fi, id = it.se;
ans[id] = st.get(i, r);
}
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << "\n";
}
}
signed main() {
if (fopen(NAME".INP", "r")) {
freopen(NAME".INP", "r", stdin);
freopen(NAME".OUT", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
int t = 1;
//cin >> t;
while (t--) {
input();
solve();
}
return 0;
}
