#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
#define kien long long
#define pb push_back
#define FOR(i, a, b) for (int i = a;i <= b; i++)
#define FORD(i, a, b) for (int i = a;i >= b; i--)
#define pii pair<int, int>
#define dembit(a) __builtin_popcountll(a)
#define task "a"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define debug(x) cout << x << " ";
#define down cout << "\n"
const kien MOD = 1e9 + 7;
const int NTEST = 100;
const int Million = 1e6 + 5;
const int MXN = 5e5 + 5;
mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
kien rand(kien l, kien r) {
assert(l <= r);
return uniform_int_distribution<kien>(l, r)(rd);
}
kien n, k, m, dem, f[MXN + 5], u, v, a[MXN];
kien maxx, minn, vtr, l, r, ans[MXN], dp[MXN];
vector <pii> qr[MXN];
vector <int> vec[MXN];
struct KBB {
kien mot, hai, ba;
};
struct segment {
KBB st[4 * MXN];
void build(int id, int l, int r) {
st[id].mot = 0;
st[id].ba = 0;
if (l == r) {
st[id].hai = a[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id].hai = max(st[id << 1].hai, st[id << 1 | 1].hai);
}
void push(int id) {
if (st[id].mot == 0) return;
for (int i = id << 1; i <= id << 1 + 1; i++) {
st[i].mot = max(st[i].mot, st[id].mot);
st[i].ba = max(st[i].ba, st[i].mot + st[i].hai);
}
}
void update(int id, int l, int r, int u, int v, kien val) {
if (u > r or v < l) return;
if (u <= l and r <= v) {
st[id].mot = max(st[id].mot, val);
st[id].ba = max(st[id].ba, st[id].mot + st[id].hai);
return;
}
push(id);
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
st[id].ba = max(st[id << 1].ba, st[id << 1 | 1].ba);
}
kien get(int id, int l, int r, int pos) {
if (l > pos) return 0;
if (r <= pos) return st[id].ba;
push(id);
int mid = (l + r) >> 1;
return max(get(id << 1, l, mid, pos), get(id << 1 | 1, mid + 1, r, pos));
}
} ST;
void solve() {
cin >> n;
FOR (i, 1, n) cin >> a[i];
ST.build(1, 1, n);
kien q; cin >> q;
FOR (i, 1, q) {
cin >> l >> r;
qr[l].pb({r, i});
}
stack <int> sk;
FOR (i, 1, n) {
while (!sk.empty() and a[sk.top()] <= a[i]) {
vec[sk.top()].pb(i); sk.pop();
}
if (!sk.empty()) vec[sk.top()].pb(i);
sk.push(i);
}
FORD (i, n - 2, 1) {
for (auto x : vec[i]) {
int thir = x * 2 - i;
if (thir <= n) ST.update(1, 1, n, thir, n, a[i] + a[x]);
// debug(thir); debug(a[i] + a[x]); down;
}
for (auto x : qr[i]) {
ans[x.second] = ST.get(1, 1, n, x.first);
}
}
FOR (i, 1, q) cout << ans[i] << "\n";
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(task".inp", "r")) {
fin(task); fou(task);
}
int t = 1; //cin >> t;
while(t--) solve();
cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}
