/*
Just consider the pair(a, b) such that with every a < k < b, a[a] > a[k] and a[b] > a[k]
The number of these pairs is just O(n): the proof can be expressed by the code finding these pairs
The rest is quite easy
*/
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
const int inf = 1e9;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );
template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }
int n;
vector<int> a;
struct Node {
int mxA, mxOth, mx;
Node(int _mxA = 0, int _mxOth = 0, int _mx = 0) : mxA(_mxA), mxOth(_mxOth), mx(_mx) {}
};
struct It {
vector<Node> node;
It(int nNode) { node.assign(nNode, 0); }
void build(int i = 1, int Left = 0, int Right = n - 1) {
if (Left == Right) {
node[i] = Node(a[Left], -inf, -inf);
return ;
}
int Mid = (Left + Right) >> 1;
build(i << 1, Left, Mid);
build(i << 1 | 1, Mid + 1, Right);
node[i].mxA = max(node[i << 1].mxA, node[i << 1 | 1].mxA);
}
void upd(int l, int r, int val, int i = 1, int Left = 0, int Right = n - 1) {
if (i != 1) {
asMx(node[i].mxOth, node[i >> 1].mxOth);
asMx(node[i].mx, node[i].mxOth + node[i].mxA);
}
if (Right < l || r < Left) return ;
if (l <= Left && Right <= r) {
asMx(node[i].mxOth, val); asMx(node[i].mx, node[i].mxOth + node[i].mxA);
return ;
}
int Mid = (Left + Right) >> 1;
upd(l, r, val, i << 1, Left, Mid);
upd(l, r, val, i << 1 | 1, Mid + 1, Right);
node[i].mx = max(node[i << 1].mx, node[i << 1 | 1].mx);
}
int getMx(int l, int r, int i = 1, int Left = 0, int Right = n - 1) {
if (i != 1) {
asMx(node[i].mxOth, node[i >> 1].mxOth);
asMx(node[i].mx, node[i].mxOth + node[i].mxA);
}
if (Right < l || r < Left) return -inf;
if (l <= Left && Right <= r) return node[i].mx;
int Mid = (Left + Right) >> 1;
return max(getMx(l, r, i << 1, Left, Mid), getMx(l, r, i << 1 | 1, Mid + 1, Right) );
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef FourLeafClover
freopen("input", "r", stdin);
#endif // FourLeafCLover
cin >> n;
a.assign(n, 0);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<vector<int> > paired(n);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (sz(st) && a[st.top()] <= a[i]) {
paired[st.top()].emplace_back(i);
st.pop();
}
if (sz(st) ) paired[st.top()].emplace_back(i);
st.emplace(i);
}
int q; cin >> q;
vector<vector<pair<int, int> > > que(n);
for (int i = 0; i < q; ++i) {
int l, r; cin >> l >> r; --l; --r;
que[l].emplace_back(r, i);
}
vector<int> ans(q);
It it( (n + 5) << 2);
it.build();
for (int i = n - 1; i >= 0; --i) {
for (int j : paired[i]) if ( (j << 1) - i <= n - 1) it.upd( (j << 1) - i, n - 1, a[i] + a[j]);
for (auto query : que[i]) ans[query.second] = it.getMx(i, query.first);
}
for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
return 0;
}
