//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#define ll long long
#define maxn 500005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int a[maxn];
int ans[maxn];
struct query{
int l, r, id;
query(){l = r = id = 0;}
query(int x, int y, int z){l = x, r = y, id = z;}
} que[maxn];
struct segtree{
int ma[4*maxn], tag[4*maxn], my[4*maxn];
void init(int cur, int l, int r) {
if (r <= l) return;
if (r - l == 1) {
ma[cur] = a[l];
my[cur] = a[l];
return;
}
int m = (l + r) / 2;
init(cur*2, l, m), init(cur*2+1, m, r);
ma[cur] = max(ma[cur*2], ma[cur*2+1]);
my[cur] = max(my[cur*2], my[cur*2+1]);
}
void push(int cur, int l, int r) {
if (tag[cur] == 0) return;
ma[cur] = max(ma[cur], my[cur] + tag[cur]);
if (r - l > 1) {
tag[cur*2] = max(tag[cur*2], tag[cur]);
tag[cur*2+1] = max(tag[cur*2+1], tag[cur]);
}
tag[cur] = 0;
}
void pull(int cur, int l, int r) {
if (r - l > 1) {
int m = (l + r) / 2;
push(cur*2, l, m), push(cur*2+1, m, r);
ma[cur] = max(ma[cur*2], ma[cur*2+1]);
}
}
void modify(int cur, int l, int r, int ql, int qr, int x) {
if (r <= l || ql >= r || qr <= l) return;
push(cur, l, r);
if (ql <= l && qr >= r) {
tag[cur] = max(tag[cur], x);
push(cur, l, r);
return;
}
int m = (l + r) / 2;
modify(cur*2, l, m, ql, qr, x), modify(cur*2+1, m, r, ql, qr, x);
pull(cur, l, r);
}
int query(int cur,int l, int r, int ql, int qr) {
if (r <= l || ql >= r || qr <= l) return 0;
push(cur, l, r);
if (ql <= l && qr >= r) {
pull(cur, l, r);
return ma[cur];
}
int m = (l + r) / 2;
return max(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
}
} seg;
int main() {
io
int n, q;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
cin >> q;
for (int i = 0;i < q;i++) {
cin >> que[i].l >> que[i].r;
que[i].id = i;
}
sort(que, que + q, [&](query x, query y){return x.l > y.l;});
stack<int> stk;
int ind = 0;
seg.init(1, 1, n+1);
for (int i = n;i >= 1;i--) {
while (stk.size() && a[i] >= a[stk.top()]) {
int val = a[i] + a[stk.top()];
seg.modify(1, 1, n+1, stk.top()*2-i, n+1, val);
stk.pop();
}
if (stk.size()) {
int val = a[i] + a[stk.top()];
seg.modify(1, 1, n+1, stk.top()*2-i, n+1, val);
}
stk.push(i);
while (ind < q && que[ind].l == i) {
ans[que[ind].id] = seg.query(1, 1, n+1, que[ind].l, que[ind].r+1);
ind++;
}
}
for (int i = 0;i < q;i++) cout << ans[i] << "\n";
}
/*
5
5 2 1 5 3
1
1 5
5
5 4 4 5 4
1
1 5
15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13
*/
