#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf32 ((int)1e9 + 7)
#define inf64 ((long long)1e18 + 7)
#define MASK32(x) (1 << (x))
#define MASK64(x) (1ll << (x))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define all(a) begin(a), end(a)
#define isz(a) ((int)a.size())
const int N = 5e5 + 5;
int a[N];
struct Query {
int l, r, i;
bool operator<(const Query& rhs) const {
return r < rhs.r;
}
} quer[N];
vector<pair<int, long long>> pairs[N];
struct Node {
long long mx_pair, mx_trip, val;
Node operator+(const Node& rhs) const {
Node res;
res.mx_pair = max(mx_pair, rhs.mx_pair);
res.mx_trip = max(mx_trip, rhs.mx_trip);
return res;
}
} seg[N << 2];
long long lazy[N];
long long res[N];
void down(int id, int l, int r) {
if(lazy[id] == 0) return;
seg[id << 1].val = lazy[id << 1] = seg[id << 1 | 1].val = lazy[id << 1 | 1] = lazy[id];
seg[id << 1].mx_trip = max(seg[id << 1].mx_trip, seg[id << 1].mx_pair + seg[id << 1].val);
seg[id << 1 | 1].mx_trip = max(seg[id << 1 | 1].mx_trip, seg[id << 1 | 1].mx_pair + seg[id << 1 | 1].val);
lazy[id] = 0;
}
void upd1(int id, int i, long long v, int l, int r) {
if(l == r) {
seg[id].mx_pair = max(seg[id].mx_pair, v);
return;
}
down(id, l, r);
int mid = (l + r) >> 1;
if(i <= mid) upd1(id << 1, i, v, l, mid);
else upd1(id << 1 | 1, i, v, mid + 1, r);
seg[id] = seg[id << 1] + seg[id << 1 | 1];
}
void upd2(int id, int x, int y, long long v, int l, int r) {
if(x <= l && r <= y) {
seg[id].mx_trip = max(seg[id].mx_trip, seg[id].mx_pair + v);
seg[id].val = lazy[id] = v;
return;
}
down(id, l, r);
int mid = (l + r) >> 1;
if(x <= mid) upd2(id << 1, x, y, v, l, mid);
if(y > mid) upd2(id << 1 | 1, x, y, v, mid + 1, r);
seg[id] = seg[id << 1] + seg[id << 1 | 1];
}
long long get(int id, int x, int y, int l, int r) {
if(x <= l && r <= y) return seg[id].mx_trip;
down(id, l, r);
int mid = (l + r) >> 1;
if(y <= mid) return get(id << 1, x, y, l, mid);
if(x > mid) return get(id << 1 | 1, x, y, mid + 1, r);
return max(get(id << 1, x, y, l, mid), get(id << 1 | 1, x, y, mid + 1, r));
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
vector<int> st1;
for(int i = 1; i <= n; ++i) {
while(!st1.empty() && a[st1.back()] < a[i]) st1.pop_back();
if(!st1.empty()) pairs[i * 2 - st1.back()].push_back({st1.back(), a[st1.back()] + a[i]});
st1.push_back(i);
}
vector<int> st2;
for(int i = n; i >= 1; --i) {
while(!st2.empty() && a[st2.back()] < a[i]) st2.pop_back();
if(!st2.empty()) pairs[st2.back() * 2 - i].push_back({i, a[st2.back()] + a[i]});
st2.push_back(i);
}
int q;
cin >> q;
for(int i = 1; i <= q; ++i) {
cin >> quer[i].l >> quer[i].r;
quer[i].i = i;
}
sort(quer + 1, quer + q + 1);
for(int i = 1, j = 1; i <= q; ++i) {
while(j <= quer[i].r) {
for(auto [k, v] : pairs[j]) upd1(1, k, v, 1, n);
upd2(1, 1, j, a[j], 1, n);
++j;
res[quer[i].i] = get(1, quer[i].l, quer[i].r, 1, n);
}
res[quer[i].i] = get(1, quer[i].l, quer[i].r, 1, n);
}
for(int i = 1; i <= q; ++i) cout << res[i] << endl;
return 0;
}
