#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 500'010;
namespace seg {
struct node {
int ans, mxab, mxc;
} t[N*4];
int sz;
node merge(const node &l, const node &r) {
node ans;
ans.ans = max({l.ans, r.ans, l.mxab + r.mxc});
ans.mxab = max(l.mxab, r.mxab);
ans.mxc = max(l.mxc, r.mxc);
return ans;
}
void merge(int i) { t[i] = merge(t[2*i+1], t[2*i+2]); }
void init(const vector<int> &vec, int i, int b, int e) {
if (e-b == 1) {
t[i].ans = t[i].mxc = vec[b];
t[i].mxab = 0;
return;
}
init(vec, 2*i+1, b, (b+e)/2);
init(vec, 2*i+2, (b+e)/2, e);
merge(i);
}
void init(const vector<int> &vec) {
sz = vec.size();
init(vec, 0, 0, sz);
}
void up(int p, int x, int i, int b, int e) {
if (e-b == 1) {
t[i].mxab = max(t[i].mxab, x);
t[i].ans = t[i].mxab + t[i].mxc;
return;
}
if (p < (b+e)/2)
up(p, x, 2*i+1, b, (b+e)/2);
else
up(p, x, 2*i+2, (b+e)/2, e);
merge(i);
}
void up(int p, int x) { up(p, x, 0, 0, sz); }
node get(int l, int r, int i, int b, int e) {
if (l <= b && e <= r)
return t[i];
if (l < (b+e)/2 && (b+e)/2 < r) {
return merge(get(l, r, 2*i+1, b, (b+e)/2),
get(l, r, 2*i+2, (b+e)/2, e));
}
if (l < (b+e)/2)
return get(l, r, 2*i+1, b, (b+e)/2);
else
return get(l, r, 2*i+2, (b+e)/2, e);
}
int get(int l, int r) { return get(l, r, 0, 0, sz).ans; }
}
vector<pii> ab[N];
vector<pii> Q[N];
int ans[N];
int a[N];
int n, q;
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n;
Loop (i,0,n)
cin >> a[i];
cin >> q;
Loop (i,0,q) {
int l, r;
cin >> l >> r;
--l;
Q[l].push_back({i,r});
}
vector<int> st;
Loop (i,0,n) {
while (st.size() && a[st.back()] < a[i])
st.pop_back();
if (st.size())
ab[st.back()].push_back({a[i] + a[st.back()], 2*i - st.back()});
st.push_back(i);
}
st.clear();
LoopR (i,0,n) {
while (st.size() && a[st.back()] <= a[i])
st.pop_back();
if (st.size())
ab[i].push_back({a[i] + a[st.back()], 2*st.back()-i});
st.push_back(i);
}
seg::init(vector<int>(a, a+n));
LoopR (i,0,n) {
for (auto [sum, pos] : ab[i]) {
if (pos >= n)
continue;
seg::up(pos, sum);
}
for (auto [q, r] : Q[i])
ans[q] = seg::get(i, r);
}
Loop (i,0,q)
cout << ans[i] << '\n';
}
