#include <bits/stdc++.h>
using namespace std;
int n;
long long arr[500005];
vector<pair<int,int> > abpairs;
long long ans[500005];
vector<pair<pair<int,int>,int> > queries;
struct node{
int s,e;
long long ab,c,abc;
node *l,*r;
node(int _s, int _e){
s = _s;
e = _e;
if (s==e){
c = arr[s];
ab = -999999999999LL;
abc = -999999999999LL;
}
else{
l = new node(s,(s+e)/2);
r = new node((s+e)/2+1,e);
mergeval();
}
}
void mergeval(){
if (s==e){
abc = ab+c;
}
else{
ab = max(l->ab,r->ab);
c = max(l->c,r->c);
abc = max(max(l->abc,r->abc),l->ab+r->c);
}
}
void upd(int pos, long long val){
if (s==e){
ab = max(ab,val);
}
else if (pos>(s+e)/2){
r->upd(pos,val);
}
else{
l->upd(pos,val);
}
mergeval();
}
pair<long long,pair<long long,long long> > query(int a, int b){
if (a<=s && e<=b){
return {abc,{ab,c}};
}
if (b<=(s+e)/2){
return l->query(a,b);
}
if (a>(s+e)/2){
return r->query(a,b);
}
auto lv = l->query(a,b);
auto rv = r->query(a,b);
return {max(max(lv.first,rv.first),lv.second.first+rv.second.second),{max(lv.second.first,rv.second.first),max(lv.second.second,rv.second.second)}};
}
}*root;
int main(){
scanf("%d",&n);
for (int x = 0; x<n; x++){
scanf("%lld",&arr[x]);
}
root = new node(0,n+3);
stack<long long> st;
for (int x = 0; x<n; x++){
if (st.empty()){
st.push(x);
continue;
}
while ((!st.empty()) && arr[x]>=arr[st.top()]){
abpairs.push_back({st.top(),x});
st.pop();
}
if (!st.empty()){
abpairs.push_back({st.top(),x});
}
st.push(x);
}
sort(abpairs.begin(),abpairs.end());
int q;
scanf("%d",&q);
for (int x = 0; x<q; x++){
int a,b;
scanf("%d%d",&a,&b);
a--;b--;
queries.push_back({{a,b},x});
}
sort(queries.begin(),queries.end());
int c = abpairs.size()-1;
for (int x = q-1; x>=0; x--){
while (c>=0 && abpairs[c].first>=queries[x].first.first){
int pos = abpairs[c].second*2-abpairs[c].first;
root->upd(min(pos,n+1),arr[abpairs[c].first]+arr[abpairs[c].second]);
//printf("upd %d, %d\n",min(pos,n+1),arr[abpairs[c].first]+arr[abpairs[c].second]);
c--;
}
ans[queries[x].second] = root->query(queries[x].first.first,queries[x].first.second).first;
}
for (int x = 0; x<q; x++){
printf("%lld\n",ans[x]);
}
}
