#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#if 1
const int MOD = (int) 998244353;
inline int lgput(int a, int b) {
int ans = 1;
while(b > 0) {
if(b & 1) ans = (1LL * ans * a) % MOD;
b >>= 1;
a = (1LL * a * a) % MOD;
}
return ans;
}
inline void mod(int &x) {
if(x >= MOD)
x -= MOD;
}
inline void add(int &x, int y) {
x += y;
mod(x);
}
inline void sub(int &x, int y) {
x += MOD - y;
mod(x);
}
inline void mul(int &x, int y) {
x = (1LL * x * y) % MOD;
}
inline int inv(int x) {
return lgput(x, MOD - 2);
}
#endif
#if 0
int fact[], invfact[];
inline void prec(int n) {
fact[0] = 1;
for(int i = 1; i <= n; i++) {
fact[i] = (1LL * fact[i - 1] * i) % MOD;
}
invfact[n] = lgput(fact[n], MOD - 2);
for(int i = n - 1; i >= 0; i--) {
invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
}
}
inline int comb(int n, int k) {
if(n < k) return 0;
return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}
#endif
using namespace std;
const int INF = 1e9;
struct Node {
int best;
int mx, lazy;
Node() {
best = mx = lazy = -INF;
}
};
struct SegTree {
vector <Node> aint;
int n;
inline void init(int _n) {
n = _n;
aint.resize(4 * n + 1);
}
inline Node combine(Node a, Node b) {
Node ans;
ans.best = max(max(a.best, b.best), max(a.mx + a.lazy, b.mx + b.lazy));
ans.mx = max(a.mx, b.mx);
return ans;
}
inline void push(int nod) {
if(2 * nod + 1 <= 4 * n) {
aint[2 * nod].lazy = max(aint[2 * nod].lazy, aint[nod].lazy);
aint[2 * nod + 1].lazy = max(aint[2 * nod + 1].lazy, aint[nod].lazy);
}
aint[nod].best = max(aint[nod].best, aint[nod].mx + aint[nod].lazy);
aint[nod].lazy = -INF;
}
void build(int nod, int left, int right, vector <int> &a) {
if(left == right) {
aint[nod].mx = a[left];
}
else {
int mid = (left + right) / 2;
build(2 * nod, left, mid, a);
build(2 * nod + 1, mid + 1, right, a);
aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
}
}
void update(int nod, int left, int right, int l, int r, int val) {
push(nod);
if(left > r || right < l) return ;
if(l <= left && right <= r) {
aint[nod].lazy = max(aint[nod].lazy, val);
push(nod);
return ;
}
int mid = (left + right) / 2;
update(2 * nod, left, mid, l, r, val);
update(2 * nod + 1, mid + 1, right, l, r, val);
aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
}
int query(int nod, int left, int right, int l, int r) {
push(nod);
if(left > r || right < l) return -INF;
if(l <= left && right <= r) {
return aint[nod].best;
}
int mid = (left + right) / 2;
int ans = max(query(2 * nod, left, mid, l, r), query(2 * nod + 1, mid + 1, right, l, r));
aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
return ans;
}
};
int main() {
#ifdef HOME
ifstream cin("A.in");
ofstream cout("A.out");
#endif
int i, n, q;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
vector <int> a(n + 1);
for(i = 1; i <= n; i++) {
cin >> a[i];
}
stack <int> stk;
vector <int> nxt(n + 1);
for(i = 1; i <= n; i++) {
while(stk.size() && a[stk.top()] < a[i]) {
nxt[stk.top()] = i;
stk.pop();
}
stk.push(i);
}
while(stk.size()) {
nxt[stk.top()] = n + 1;
stk.pop();
}
struct Segm {
int l, r;
bool operator <(const Segm &other) const {
return l > other.l;
}
};
vector <Segm> segm;
for(i = 1; i <= n; i++) {
int p = i + 1, mx = 0;
while(p <= n && a[i] > mx) {
segm.push_back({i, p});
mx = max(mx, a[p]);
p = nxt[p];
}
}
sort(segm.begin(), segm.end());
cin >> q;
struct Query {
int l, r, pos;
bool operator <(const Query &other) const {
return l > other.l;
}
};
vector <Query> qry(q);
for(i = 0; i < q; i++) {
cin >> qry[i].l >> qry[i].r;
qry[i].pos = i + 1;
}
sort(qry.begin(), qry.end());
vector <int> sol(q + 1);
int pos = 0, sz = segm.size();
SegTree st; st.init(n);
st.build(1, 1, n, a);
for(i = 0; i < q; i++) {
while(pos < sz && segm[pos].l >= qry[i].l) {
if(2 * segm[pos].r - segm[pos].l <= n) {
st.update(1, 1, n, 2 * segm[pos].r - segm[pos].l, n, a[segm[pos].l] + a[segm[pos].r]);
}
pos++;
}
sol[qry[i].pos] = st.query(1, 1, n, qry[i].l + 2, qry[i].r);
}
for(i = 1; i <= q; i++) {
cout << sol[i] << "\n";
}
return 0;
}
