#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pi pair<int, int>
#define vi vector<int>
#define pb push_back
//max1 = A + B, max2 = C, max3 = A + B + C
struct node {
int max1, max2, max3;
};
constexpr int base = (1 << 19);
constexpr int LIM = 5e5;
node INF;
node tri[2 * base];
int tab[LIM + 10];
vi can[LIM + 10];
vector<pi> zap[LIM + 10];
int ans[LIM + 10];
int lasy[2 * base];
node merge(node a, node b) {
node res;
res.max1 = max(a.max1, b.max1);
res.max2 = max(a.max2, b.max2);
res.max3 = max({a.max3, b.max3, a.max1 + b.max2});
return res;
}
void spl(int v) {
tri[2 * v].max1 = max(tri[2 * v].max1, lasy[v]);
tri[2 * v].max3 = max(tri[2 * v].max3, lasy[v] + tri[2 * v].max2);
tri[2 * v + 1].max1 = max(tri[2 * v + 1].max1, lasy[v]);
tri[2 * v + 1].max3 = max(tri[2 * v + 1].max3, lasy[v] + tri[2 * v + 1].max2);
lasy[2 * v] = max(lasy[2 * v], lasy[v]);
lasy[2 * v + 1] = max(lasy[2 * v + 1], lasy[v]);
}
void upd(int v, int l, int r, int a, int b, int x) {
if(l > b || r < a) {
return;
}
if(a <= l && r <= b) {
tri[v].max1 = max(tri[v].max1, x);
tri[v].max3 = max(tri[v].max3, x + tri[v].max2);
lasy[v] = max(lasy[v], x);
return;
}
spl(v);
int mid = (l + r) / 2;
upd(2 * v, l, mid, a, b, x);
upd(2 * v + 1, mid + 1, r, a, b, x);
tri[v] = merge(tri[2 * v], tri[2 * v + 1]);
}
node res;
void query(int v, int l, int r, int a, int b) {
if(l > b || r < a) {
return;
}
if(a <= l && r <= b) {
res = merge(res, tri[v]);
return;
}
spl(v);
int mid = (l + r) / 2;
query(2 * v, l, mid, a, b);
query(2 * v + 1, mid + 1, r, a, b);
tri[v] = merge(tri[2 * v], tri[2 * v + 1]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
INF.max1 = -1e9, INF.max2 = -1e9, INF.max3 = -1e9;
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> tab[i];
tri[i + base - 1] = INF;
tri[i + base - 1].max2 = tab[i];
}
for(int i = base - 1; i >= 1; i--) {
tri[i] = merge(tri[2 * i], tri[2 * i + 1]);
}
stack<int>s;
for(int i = 1; i <= n; i++) {
while(!s.empty() && tab[s.top()] <= tab[i]) {
can[s.top()].pb(i);
s.pop();
}
if(!s.empty()) {
can[s.top()].pb(i);
}
s.push(i);
}
int t;
cin >> t;
for(int i = 1; i <= t; i++) {
int l, r;
cin >> l >> r;
zap[l].pb({r, i});
}
for(int i = n; i >= 1; i--) {
for(auto x : can[i]) {
upd(1, 1, base, 2 * x - i, n, tab[i] + tab[x]);
}
for(auto x : zap[i]) {
res = INF;
query(1, 1, base, i, x.st);
ans[x.nd] = res.max3;
}
}
for(int i = 1; i <= t; i++) {
cout << ans[i] << '\n';
}
}
