#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
constexpr ll inf = 1ll << 62ll;
mt19937 mt(time(0));
ll _ = 0;
struct segtree {
struct node {
ll mx = -inf, bord = -inf, lz_mx = -inf;
};
ll nt;
vector<node> tree;
segtree(vector<ll> &a) {
nt = 1;
while (nt < sz(a)) nt *= 2;
tree = vector<node>(2*nt);
for (ll i = 0; i < sz(a); i++) {
tree[nt+i].mx = a[i] - inf;
}
for (ll i = nt-1; i > 0; i--) {
recalc(i);
}
}
void recalc(ll k) {
assert(k < nt);
tree[k].mx = max(tree[2*k].mx, tree[2*k+1].mx);
ll dl = tree[k].mx - tree[2*k].mx;
ll dr = tree[k].mx - tree[2*k+1].mx;
tree[k].bord = min(tree[2*k].bord + dl, tree[2*k+1].bord + dr);
}
void prop(ll k) {
if (k < nt) {
tree[2*k].lz_mx = max(tree[2*k].lz_mx, tree[k].lz_mx);
tree[2*k+1].lz_mx = max(tree[2*k+1].lz_mx, tree[k].lz_mx);
}
if (tree[k].lz_mx <= tree[k].bord) return;
ll diff = tree[k].lz_mx - tree[k].bord;
tree[k].mx += diff;
tree[k].bord += diff;
}
void range_update_max(ll l, ll r, ll v) { return range_update_max(1, 0, nt-1, l, r, v); }
void range_update_max(ll k, ll tl, ll tr, ll l, ll r, ll v) {
prop(k);
if (r < tl || l > tr) return;
if (l <= tl && r >= tr) {
tree[k].lz_mx = max(tree[k].lz_mx, v);
prop(k);
return;
}
ll mid = tl + (tr - tl) / 2;
range_update_max(2*k, tl, mid, l, r, v);
range_update_max(2*k+1, mid+1, tr, l, r, v);
recalc(k);
}
ll range_query_max(ll l, ll r) { return range_query_max(1, 0, nt-1, l, r); }
ll range_query_max(ll k, ll tl, ll tr, ll l, ll r) {
prop(k);
if (r < tl || l > tr) return -inf;
if (l <= tl && r >= tl) return tree[k].mx;
ll mid = tl + (tr - tl) / 2;
return max(range_query_max(2*k, tl, mid, l, r), range_query_max(2*k+1, mid+1, tr, l, r));
}
};
void solve() {
ll n; cin >> n;
vector<ll> a(n);
for (auto &e : a) cin >> e;
ll q; cin >> q;
vector<array<ll, 3>> queries(q); // {l, r, qid}
ll t = 0; for (auto &[l, r, qid] : queries) cin >> l >> r, l--, r--, qid = t++;
sort(all(queries), [&](array<ll, 3> a, array<ll, 3> b) { return a[0] > b[0]; });
stack<pll> dec_stk; // {id, val}
vector<pll> pairs; // {l, m}
for (ll i = n-1; i >= 0; i--) {
while (sz(dec_stk) && dec_stk.top().second <= a[i]) {
// ...
ll mn_id = i + (dec_stk.top().first - i) * 2;
if (mn_id < n) pairs.emplace_back(i, dec_stk.top().first);
dec_stk.pop();
}
if (sz(dec_stk)) {
// ...
ll mn_id = i + (dec_stk.top().first - i) * 2;
if (mn_id < n) pairs.emplace_back(i, dec_stk.top().first);
}
dec_stk.emplace(i, a[i]);
}
sort(all(pairs));
segtree tree(a);
vector<ll> res(q);
ll ptr = sz(pairs)-1;
for (auto &[l, r, qid] : queries) {
while (ptr >= 0 && pairs[ptr].first >= l) {
auto [pl, pm] = pairs[ptr];
ll pr = pl + (pm - pl) * 2;
tree.range_update_max(pr, n-1, a[pl] + a[pm]);
ptr--;
}
res[qid] = tree.range_query_max(l, r);
}
for (auto &e : res) cout << e << '\n';
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
solve();
}
