#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int a[maxn];
vector <int> qr[maxn];
vector <pair <int, int>> v[maxn];
int res[maxn], opt[maxn];
int l[maxn], r[maxn];
int n;
struct node {
int mxpair, maxv, opt;
node () {}
node (int mxpair, int maxv, int opt) : mxpair(mxpair), maxv(maxv), opt(opt) {}
};
node operator + (node p, node q) {
node ans;
ans.maxv = max(p.maxv, q.maxv);
ans.mxpair = max(p.mxpair, q.mxpair);
ans.opt = max(p.opt, q.opt);
ans.opt = max(ans.opt, p.mxpair + q.maxv);
return ans;
}
node t[maxn * 4];
void build(int c = 1, int b = 1, int e = n) {
if(b == e) {
t[c].mxpair = 0;
t[c].opt = t[c].maxv = a[b];
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
build(l, b, m);
build(r, m + 1, e);
t[c] = t[l] + t[r];
}
void update(int x, int val, int c = 1, int b = 1, int e = n) {
if(b == e) {
t[c].mxpair = max(t[c].mxpair, val);
t[c].opt = t[c].mxpair + t[c].maxv;
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) update(x, val, l, b, m);
else update(x, val, r, m + 1, e);
t[c] = t[l] + t[r];
}
node query(int x, int y, int c = 1, int b = 1, int e = n) {
if(x <= b && e <= y) {
return t[c];
}
if(y < b || e < x) return node( 0, 0, 0);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
return query(x, y, l, b, m) + query(x, y, r, m + 1, e);
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
int q;
cin >> q;
for(int i = 1; i <= q; i++) {
cin >> l[i] >> r[i];
qr[l[i]].emplace_back(i);
}
stack <int> s;
vector <pair <int, int>> imp;
for(int i = 1; i <= n; i++) {
while(!s.empty() && a[s.top()] <= a[i]) {
imp.emplace_back(s.top(), i);
s.pop();
}
if(!s.empty()) imp.emplace_back(s.top(), i);
s.push(i);
}
for(auto i : imp) {
if(2 * i.second - i.first <= n) {
v[i.first].emplace_back(2 * i.second - i.first,
a[i.first] + a[i.second]);
}
}
build();
for(int i = n; i >= 1; i--) {
for(auto j : v[i]) {
if(j.first <= n) {
update(j.first, j.second);
}
}
for(auto j : qr[i]) {
res[j] = query(l[j], r[j]).opt;
}
}
for(int i = 1; i <= q; i++) {
cout << res[i] << endl;
}
return 0;
}
