#include <bits/stdc++.h>
using namespace std;
#define int long long
using ii = pair<int, int>;
const int N = 5e5 + 5;
int n, q, a[N], st[N<<2], mx[N<<2], lz[N<<2], res[N];
vector<ii> query[N];
void build(int tl = 1, int tr = n, int i = 1){
if(tl == tr){
mx[i] = a[tl];
return;
}
int tm = tl + tr >> 1;
build(tl, tm, i<<1); build(tm + 1, tr, i<<1|1);
mx[i] = max(mx[i<<1], mx[i<<1|1]);
}
void push(int i){
if(!lz[i]) return;
st[i<<1] = max(st[i<<1], lz[i] + mx[i<<1]);
st[i<<1|1] = max(st[i<<1|1], lz[i] + mx[i<<1|1]);
lz[i<<1] = max(lz[i<<1], lz[i]); lz[i<<1|1] = max(lz[i<<1|1], lz[i]); lz[i] = 0;
}
void update(int l, int r, int x, int tl = 1, int tr = n, int i = 1){
if(r < tl || tr < l || l > r) return;
if(l <= tl && tr <= r){
st[i] = max(st[i], x + mx[i]);
lz[i] = max(lz[i], x);
return;
}
push(i);
int tm = tl + tr >> 1;
update(l, r, x, tl, tm, i<<1); update(l, r, x, tm + 1, tr, i<<1|1);
st[i] = max(st[i<<1], st[i<<1|1]);
}
int get(int l, int r, int tl = 1, int tr = n, int i = 1){
if(r < tl || tr < l || l > r) return 0;
if(l <= tl && tr <= r) return st[i];
push(i);
int tm = tl + tr >> 1;
return max(get(l, r, tl, tm, i<<1), get(l, r, tm + 1, tr, i<<1|1));
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
// #define task "test"
// if(fopen(task ".inp", "r")){
// freopen(task ".inp", "r", stdin);
// freopen(task ".out", "w", stdout);
// }
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> q;
for(int i = 1; i <= q; i++){
int l, r; cin >> l >> r;
query[l].push_back({r, i});
}
build();
stack<int> s;
for(int i = n; i >= 1; i--){
while(s.size()){
update(2*s.top() - i, n, a[i] + a[s.top()]);
if(a[s.top()] <= a[i]) s.pop();
else break;
}
s.push(i);
for(auto [r, idx] : query[i]) res[idx] = get(i, r);
}
for(int i = 1; i <= q; i++) cout << res[i] << "\n";
}
