#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Query {
int l, r, idx;
Query(){}
Query(int l, int r, int idx): l(l), r(r), idx(idx){}
};
struct segTree{
struct Node{
int l, r, v;
Node(){}
Node(int l, int r, int v): l(l), r(r), v(v){}
Node operator+(const Node &nxt)const{
return Node(max(l, nxt.l), max(r, nxt.r), max({v, nxt.v, l+nxt.r}));
}
} tree[2000002];
void init(int i, int l, int r, int *arr){
if(l==r){
tree[i] = Node(-1e9, arr[l], -1e9);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, arr);
init(i*2+1, m+1, r, arr);
tree[i] = tree[i*2] + tree[i*2+1];
}
Node query(int i, int l, int r, int s, int e){
if(r<s || e<l) return Node(-1e9, -1e9, -1e9);
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
}
void update(int i, int l, int r, int x, int v){
if(l==r){
tree[i].l = max(tree[i].l, v);
tree[i].v = max(tree[i].v, tree[i].l+tree[i].r);
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
tree[i] = tree[i*2] + tree[i*2+1];
}
} tree;
int n, q;
int arr[500002];
vector<int> interval[500002];
vector<Query> query[500002];
int ans[500002];
void makeInterval(){
vector<pair<int, int> > vec;
for(int i=1; i<=n; i++){
while(!vec.empty() && vec.back().second <= arr[i]){
interval[vec.back().first].push_back(i);
vec.pop_back();
}
if(!vec.empty()) interval[vec.back().first].push_back(i);
vec.push_back(make_pair(i, arr[i]));
}
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
makeInterval();
scanf("%d", &q);
for(int i=1; i<=q; i++){
int l, r;
scanf("%d %d", &l, &r);
query[l].push_back(Query(l, r, i));
}
tree.init(1, 1, n, arr);
for(int i=n-2; i>=1; i--){
for(int j: interval[i]){
if(2*j-i>n) continue;
tree.update(1, 1, n, 2*j-i, arr[i]+arr[j]);
}
for(Query p: query[i]){
ans[p.idx] = tree.query(1, 1, n, i, p.r).v;
}
}
for(int i=1; i<=q; i++){
printf("%d\n", ans[i]);
}
}
