#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 5e5 + 5;
struct viet{
ll a, b, v;
};
viet st[N * 4];
ll a[N], ans[N];
vector<pair<ll, ll>> mem[N], qr[N];
void Init(ll k, ll l, ll r){
if (l == r){
st[k].a = a[l];
return;
}
ll mid = (l + r) >> 1;
Init(k << 1, l, mid);
Init(k << 1 | 1, mid + 1, r);
st[k].a = max(st[k << 1].a, st[k << 1 | 1].a);
}
void down(ll k){
st[k << 1].b = max(st[k << 1].b, st[k].b);
st[k << 1].v = max(st[k << 1].v, st[k << 1].a + st[k << 1].b);
st[k << 1 | 1].b = max(st[k << 1 | 1].b, st[k].b);
st[k << 1 | 1].v = max(st[k << 1 | 1].v, st[k << 1 | 1].a + st[k << 1 | 1].b);
}
void upd(ll k, ll l, ll r, ll x, ll y, ll v){
if (x > r || y < l) return;
if (l != r) down(k);
if (x <= l && y >= r){
st[k].b = max(st[k].b, v);
st[k].v = max(st[k].v, st[k].b + st[k].a);
return;
}
ll mid = (l + r) >> 1;
upd(k << 1, l, mid, x, y, v);
upd(k << 1 | 1, mid + 1, r, x, y, v);
st[k].v = max(st[k << 1].v, st[k << 1 | 1].v);
}
ll get(ll k, ll l, ll r, ll x, ll y){
if (x > r || y < l) return 0;
if (l != r) down(k);
if (x <= l && y >= r) return st[k].v;
ll mid = (l + r) >> 1;
return max(get(k << 1, l, mid, x, y), get(k << 1 | 1, mid + 1, r, x, y));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("balance.in", "r")){
freopen("balance.in", "r", stdin);
freopen("balance.out", "w", stdout);
}
ll n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
stack<ll> s;
for (int i = 1; i <= n; i++){
while (s.size()){
if (a[s.top()] <= a[i]){
ll k = 2 * i - s.top();
if (k <= n) mem[s.top()].push_back({k, a[i] + a[s.top()]});
} else break;
s.pop();
}
if (s.size()){
ll k = 2 * i - s.top();
if (k <= n) mem[s.top()].push_back({k, a[i] + a[s.top()]});
}
s.push(i);
}
ll q;
cin >> q;
for (int i = 1; i <= q; i++){
ll l, r;
cin >> l >> r;
qr[l].push_back({r, i});
}
Init(1, 1, n);
for (int i = n; i >= 1; i--){
for (auto j : mem[i]){
upd(1, 1, n, j.first, n, j.second);
}
for (auto j : qr[i]){
ans[j.second] = get(1, 1, n, i, j.first);
}
}
for (int i = 1; i <= q; i++) cout << ans[i] << endl;
}
/*
*/
