//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
llo n;
llo it[500001];
llo aa[500001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(llo i=0;i<n;i++){
cin>>it[i];
}
vector<pair<llo,llo>> ss;
aa[n-1]=it[n-1];
for(llo i=n-2;i>=0;i--){
aa[i]=max(aa[i+1],it[i]);
}
llo ans=0;
for(llo i=0;i<n;i++){
while(ss.size()){
if(ss.back().a<it[i]){
ss.pop_back();
}
else{
break;
}
}
if(ss.size()){
llo ind=i-ss.back().b+i;
if(i<n){
ans=max(ans,it[i]+ss.back().a+aa[ind]);
}
}
ss.pb({it[i],i});
}
ss.clear();
for(llo i=n-1;i>=0;i--){
while(ss.size()){
if(ss.back().a<it[i]){
ss.pop_back();
}
else{
break;
}
}
if(ss.size()){
llo ind=ss.back().b-i+ss.back().b;
if(i<n){
ans=max(ans,it[i]+ss.back().a+aa[ind]);
}
}
ss.pb({it[i],i});
}
llo q;
cin>>q;
while(q--){
llo cc,dd;
cin>>cc>>dd;
cc--;
dd--;
cout<<ans<<endl;
}
return 0;
}
