#include "bits/stdc++.h"
using namespace std;
const int maxn = 5e5 + 5;
const int inf = 1e9;
int n, q, a[maxn];
vector<pair<int, int>> cand;
int ans[maxn];
struct node {
int res, ft, se;
node() {
res = ft = se = 0;
}
node(int x, int y, int z) : res(x), ft(y), se(z) {}
node operator+(const node &o) const {
node tmp = *this;
tmp.res = max({tmp.res, o.res, this->ft + o.se});
tmp.se = max(tmp.se, o.se);
tmp.ft = max(tmp.ft, o.ft);
return tmp;
}
} tree[maxn * 4];
struct segment_tree {
int n;
segment_tree() {}
segment_tree(int n) : n(n) {}
void build(int ind, int l, int r) {
if(l == r) {
tree[ind].res = tree[ind].se = a[l];
return;
}
int mid = (l + r) / 2;
build(ind * 2, l, mid);
build(ind * 2 + 1, mid + 1, r);
tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
}
void update(int ind, int l, int r, int pos, int val) {
if(l == r) {
tree[ind].ft = max(tree[ind].ft, val);
tree[ind].res = tree[ind].ft + tree[ind].se;
return;
}
int mid = (l + r) / 2;
if(pos <= mid) update(ind * 2, l, mid, pos, val);
else update(ind * 2 + 1, mid + 1, r, pos, val);
tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
}
node get(int ind, int l, int r, int x, int y) {
if(l > y || r < x) return node();
if(x <= l and r <= y) return tree[ind];
int mid = (l + r) / 2;
return get(ind * 2, l, mid, x, y) + get(ind * 2 + 1, mid + 1, r, x, y);
}
void update(int pos, int val) {
update(1, 1, n, pos, val);
}
node get(int x, int y) {
return get(1, 1, n, x, y);
}
} st;
struct query {
int l, r, id;
bool operator<(const query &o) {
return l > o.l;
}
} que[maxn];
void solve() {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
stack<int> s;
for(int i = 1; i <= n; ++i) {
while(!s.empty() and a[i] >= a[s.top()]) {
cand.push_back({s.top(), i * 2 - s.top()});
s.pop();
}
if(!s.empty()) {
cand.push_back({s.top(), i * 2 - s.top()});
}
s.push(i);
}
st = segment_tree(n);
st.build(1, 1, n);
cin >> q;
for(int i = 1; i <= q; ++i) {
cin >> que[i].l >> que[i].r;
que[i].id = i;
}
sort(que + 1, que + q + 1);
sort(cand.begin(), cand.end(), [](const pair<int, int> &x, const pair<int, int> &y) -> bool {
return x.first > y.first;
});
int j = 0;
for(int i = 1; i <= q; ++i) {
while(j < (int)cand.size() and cand[j].first >= que[i].l) {
int x = cand[j].first, y = cand[j].second;
int z = (y + x) / 2;
if(y <= n) st.update(y, a[x] + a[z]);
++j;
// cerr << x << " " << z << " " << y << '\n';
}
ans[que[i].id] = st.get(que[i].l, que[i].r).res;
}
for(int i = 1; i <= q; ++i) {
cout << ans[i] << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
