#include <bits/stdc++.h>
using namespace std;
const int nmax = 5e5 + 5;
const int nextpow = 1 << 20;
const int inf = 1e9;
int n;
vector<int> v;
namespace AINT {
struct Node {
int vab, x, sum;
Node operator +(const Node& a) const {
return Node{-inf, max(x, a.x), max(sum, a.sum)};
}
void tag(const int& a) {
if(vab < a)
vab = a, sum = max(sum, a + x);
}
} aint[nmax * 4], iden = Node{-inf, -inf, -inf};
int lazy[nmax * 4];
void apply(int node, int cl, int cr) {
if(lazy[node] == -1)
return;
aint[node].tag(lazy[node]);
if(cl != cr) {
lazy[2 * node] = max(lazy[node], lazy[2 * node]);
lazy[2 * node + 1] = max(lazy[node], lazy[2 * node + 1]);
}
aint[node] = aint[node] + aint[2 * node] + aint[2 * node + 1];
lazy[node] = -1;
}
void prop(int node, int cl, int cr) {
apply(node, cl, cr);
if(cl == cr)
return;
int mid = cl + cr >> 1;
apply(2 * node, cl, mid);
apply(2 * node + 1, mid + 1, cr);
}
void upd(int l, int r, int val, int node = 1, int cl = 0, int cr = n) {
prop(node, cl, cr);
if(cr < l || r < cl)
return;
if(l <= cl && cr <= r) {
//cout << "cine " << l << ' ' << cl << ' ' << cr << ' ' << r << " +" << val << '\n';
lazy[node] = val;
prop(node, cl, cr);
return;
}
int mid = cl + cr >> 1;
upd(l, r, val, 2 * node, cl, mid);
upd(l, r, val, 2 * node + 1, mid + 1, cr);
int sus = aint[node].vab;
aint[node] = aint[2 * node] + aint[2 * node + 1];
aint[node].vab = sus;
}
Node query(int l, int r, int node = 1, int cl = 0, int cr = n) {
prop(node, cl, cr);
if(cr < l || r < cl)
return iden;
if(l <= cl && cr <= r) {
//cout << "cum " << l << ' ' << cl << ' ' << cr << ' ' << r << ' ' << aint[node].x << ' ' << aint[node].vab << ' ' << aint[node].sum << '\n';
return aint[node];
}
int mid = cl + cr >> 1;
Node rez = query(l, r, 2 * node, cl, mid) + query(l, r, 2 * node + 1, mid + 1, cr);
return rez;
}
int qry(int l, int r) {
return query(l, r).sum;
}
void construct(int node = 1, int cl = 0, int cr = n) {
aint[node] = iden;
lazy[node] = -1;
if(cl == cr) {
aint[node].x = v[cl];
return;
}
int mid = cl + cr >> 1;
construct(2 * node, cl, mid);
construct(2 * node + 1, mid + 1, cr);
aint[node] = aint[2 * node] + aint[2 * node + 1];
return;
}
};
vector<tuple<int,int,int> > rez;
vector<int> qs[nmax];
static void candid(int l, int r) {
int sim = r + (r - l);
if(sim >= n)
return;
//cerr << l << ' ' << r << ' ' <<sim << ' ' << n << '\n';
AINT::upd(sim, n, v[l] + v[r]);
return;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int q;
cin >> n;
v.resize(n);
#define stack deobiceicineintreaba
vector<int> stack;
for(auto &x : v) cin >> x;
stack.push_back(n);
v.push_back(-1e9 -5);
AINT::construct();
v.back() *= -1;
//cerr << v.size() << '\n',
cin >> q;
rez.resize(q);
int i = 0;
for(auto &[a, b, c] : rez)
cin >> a >> b, --a, --b, c = 0, qs[a].push_back(i++);
int l, r, val;
for(int i = n - 1; i >= 0; i--) {
while(v[stack.back()] <= v[i]) {
candid(i, stack.back());
stack.pop_back();
}
candid(i, stack.back());
stack.push_back(i);
for(auto x : qs[i]) {
tie(l, r, val) = rez[x];
val = AINT::qry(l, r);
//cout << val << '\n';
rez[x] = {l, r, val};
}
}
for(auto [a, b, c] : rez)
cout << c << '\n';
}
#warning cine cu scopul de a fucking intreba
