#include<iostream>
#include<vector>
using namespace std;
const int mininf = -1e9;
struct node{
int ma, mb, sum;
node(int _ma, int _mb, int _sum){
ma = _ma, mb = _mb, sum = _sum;
}
};
vector<node> seg;
inline node pull(node a, node b){
return node(max(a.ma, b.ma), max(a.mb, b.mb), max(max(a.sum, b.sum), a.ma + b.mb));
}
void build(int l, int r, int ind, vector<int>& vec){
if(l == r){
seg[ind].mb = vec[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, ind * 2, vec);
build(mid + 1, r, ind * 2 + 1, vec);
seg[ind] = pull(seg[ind * 2], seg[ind * 2 + 1]);
}
void modify(int l, int r, int pos, int num, int ind){
if(l == r){
seg[ind].ma = max(seg[ind].ma, num);
seg[ind].sum = max(seg[ind].sum, seg[ind].ma + seg[ind].mb);
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) modify(l, mid, pos, num, ind * 2);
else modify(mid + 1, r, pos, num, ind * 2 + 1);
seg[ind] = pull(seg[ind * 2], seg[ind * 2 + 1]);
}
node query(int l, int r, int start, int end, int ind){
if(r < start || end < l) return node(mininf, mininf, mininf);
else if(start <= l && r <= end) return seg[ind];
int mid = (l + r) >> 1;
return pull(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> vec(n + 1);
seg.resize(4 * n + 4, node(mininf, mininf, mininf));
for(int i = 1; i <= n; i++) cin >> vec[i];
build(1, n, 1, vec);
vector<vector<pair<int, int>>> sweep(n + 1), rngs(n + 1);
vector<int> st;
for(int i = 1; i <= n; i++){
while(!st.empty() && vec[st.back()] < vec[i]){
rngs[st.back()].emplace_back(i, vec[st.back()] + vec[i]);
st.pop_back();
}
if(!st.empty()){
rngs[st.back()].emplace_back(i, vec[st.back()] + vec[i]);
}
st.push_back(i);
}
int q;
cin >> q;
vector<int> ans(q);
for(int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
sweep[l].emplace_back(r, i);
}
for(int i = n; i > 0; i--){
for(auto &[b, val]: rngs[i]){
//cout << i << " " << b << "\n";
if(2 * b - i <= n) modify(1, n, 2 * b - i, val, 1);
}
for(auto &[r, id]: sweep[i]){
ans[id] = query(1, n, i, r, 1).sum;
}
}
for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}
