#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define ll long long
#define db double
#define ii pair<int,int>
#define pb push_back
#define MASK(i) (1LL << i)
#define sq(i) (1LL * (i) * (i))
#define task "khoile08"
const ll INF = 1e18;
const int inf = 1e9;
const int N = 5e5;
int n, q;
int a[N + 5];
vector<ii> query[N + 5];
struct Smt {
ll sum[4 * N + 5], mx[4 * N + 5], ans[4 * N + 5], lz[4 * N + 5];
void build(int id, int l, int r) {
if(l == r) {
mx[id] = a[l];
return;
}
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}
void push(int id) {
ll val = lz[id];
ans[id << 1] = max(ans[id << 1], val + mx[id << 1]);
ans[id << 1 | 1] = max(ans[id << 1 | 1], val + mx[id << 1 | 1]);
lz[id << 1] = max(lz[id << 1], val);
lz[id << 1 | 1] = max(lz[id << 1 | 1], val);
lz[id] = 0;
return;
}
void up(int id, int l, int r, int u, int v, ll val) {
if(l > v || r < u) return;
if(l >= u && r <= v) {
ans[id] = max(ans[id], val + mx[id]);
lz[id] = max(lz[id], val);
return;
}
push(id);
int mid = l + r >> 1;
up(id << 1, l, mid, u, v, val);
up(id << 1 | 1, mid + 1, r, u, v, val);
ans[id] = max(ans[id << 1], ans[id << 1 | 1]);
}
ll get(int id, int l, int r, int u, int v) {
if(l > v || r < u) return -INF;
if(l >= u && r <= v) return ans[id];
push(id);
int mid = l + r >> 1;
return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
};
Smt it;
stack<int> st;
ll res[N + 5];
void Solve() {
it.build(1, 1, n);
FOD(i, n, 1) {
while(!st.empty() && a[st.top()] < a[i]) {
int y = st.top();
it.up(1, 1, n, 2 * y - i, n, a[i] + a[y]);
st.pop();
}
if(st.size()) it.up(1, 1, n, 2 * st.top() - i, n, a[i] + a[st.top()]);
st.push(i);
for(auto H : query[i]) {
res[H.se] = it.get(1, 1, n, i, H.fi);
}
}
FOR(i, 1, q) cout << res[i] << '\n';
}
signed main() {
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
while(tc--) {
cin >> n;
FOR(i, 1, n) cin >> a[i];
cin >> q;
FOR(i, 1, q) {
int l, r;
cin >> l >> r;
query[l].pb({r, i});
}
Solve();
}
}
