#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int a[N];
vector<pair<int, int>> que[N];
int resenje[N];
int b[N];
pair<int, int> c[N];
int seg[4 * N - 1][2];
int lazy[4 * N - 1];
int n;
int ind = 0;
void build(int u, int l, int r) {
if (l == r) {
seg[u][1] = a[l];
return;
}
int mid = (l + r) >> 1;
build(u * 2 + 1, l, mid);
build(u * 2 + 2, mid + 1, r);
seg[u][1] = max(seg[u * 2 + 1][1], seg[u * 2 + 2][1]);
}
void upd(int u, int x) {
seg[u][0] = max(seg[u][0], x + seg[u][1]);
lazy[u] = max(lazy[u], x);
}
void shift(int u) {
if (!lazy[u])
return;
upd(u * 2 + 1, lazy[u]);
upd(u * 2 + 2, lazy[u]);
lazy[u] = 0;
}
void update(int u, int l, int r, int L, int R, int x) {
if (r < L || l > R)
return;
if (l >= L && r <= R) {
upd(u, x);
return;
}
shift(u);
int mid = (l + r) >> 1;
update(u * 2 + 1, l, mid, L, R, x);
update(u * 2 + 2, mid + 1, r, L, R, x);
seg[u][0] = max(seg[u * 2 + 1][0], seg[u * 2 + 2][0]);
}
void Update(int i) {
if (b[i]) {
int l = 2 * b[i] - i;
if (l < n) {
update(0, 0, n - 1, l, n - 1, a[i] + a[b[i]]);
}
}
while (c[ind].first == i) {
int l = 2 * c[ind].second - c[ind].first;
if (l < n) {
update(0, 0, n - 1, l, n - 1, a[c[ind].first] + a[c[ind].second]);
}
ind++;
}
}
int out(int u, int l, int r, int L, int R) {
if (r < L || l > R)
return 0;
if (l >= L && r <= R) {
return seg[u][0];
}
shift(u);
int mid = (l + r) >> 1;
return max(out(u * 2 + 1, l, mid, L, R), out(u * 2 + 2, mid + 1, r, L, R));
}
void veca(int n) {
stack<int> s;
for (int i = 0; i < n; i++) {
while (!s.empty() && a[s.top()] <= a[i]) {
b[s.top()] = i;
s.pop();
}
s.push(i);
}
}
void veca1(int n) {
stack<int> s;
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && a[s.top()] <= a[i]) {
c[ind].first = i;
c[ind++].second = s.top();
s.pop();
}
s.push(i);
}
c[ind].first = -1;
ind = 0;
}
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
return a.first.first >= b.first.first;
}
void solve() {
int q;
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;
que[l - 1].push_back({r - 1, i});
}
veca(n);
veca1(n);
build(0, 0, n - 1);
for (int i = n - 1; i >= 0; i--) {
Update(i);
for (auto j = que[i].begin(); j != que[i].end(); j++) {
pair<int, int> par = *j;
resenje[par.second] = out(0, 0, n - 1, i, par.first);
}
}
for (int i = 0; i < q; i++)
cout << resenje[i] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
