#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
const int N= 5e5+5;
int n, a[N], q;
vector<pii> qr[N];
int fans[N];
int tb[N][25];
int getmx(int l, int r){
int j = __lg(r-l+1);
return max(tb[l][j], tb[r-(1<<j)+1][j]);
}
struct SegTree{
int tr[4*N], lz[4*N];
void app_lz(int id, int l, int r, int v){
tr[id] = max(tr[id], v+getmx(l,r));
lz[id] = max(lz[id], v);
}
void down(int id, int l, int r){
if(!lz[id]) return;
int mid=(l+r)>>1;
app_lz(2*id,l,mid,lz[id]);
app_lz(2*id+1,mid+1,r,lz[id]);
lz[id] = 0;
}
void update(int id, int l, int r, int t_l, int t_r, int v){
if(l>t_r||r<t_l) return;
if(t_l<=l&&r<=t_r) {
tr[id] = max(tr[id], v+getmx(l,r));
lz[id] = max(lz[id], v);
return;
}
int mid=(l+r)>>1;
down(id,l,r);
update(2*id,l,mid,t_l,t_r,v);
update(2*id+1,mid+1,r,t_l,t_r,v);
tr[id] = max(tr[2*id], tr[2*id+1]);
}
int get(int id, int l, int r, int t_l, int t_r){
if(l>t_r||r<t_l) return 0;
if(t_l<=l&&r<=t_r) return tr[id];
int mid =(l+r)>>1;
down(id,l,r);
return max(get(2*id,l,mid,t_l,t_r), get(2*id+1,mid+1,r,t_l,t_r));
}
}st;
void preprocess(){
for(int i=n;i>=1;i--){
tb[i][0] = a[i];
for(int j=1;i+(1<<j)-1<=n;j++){
tb[i][j] = max(tb[i][j-1], tb[i+(1<<(j-1))][j-1]);
}
}
static int st[N];
for(int i=1;i<=n;i++){
while(st[0]&&a[st[st[0]]]<=a[i]){
// cerr<<st[st[0]]<<" "<<i<<"\n";
qr[st[st[0]--]].pb({i,0});
}
if(st[0]){
qr[st[st[0]]].pb({i,0});
}
st[++st[0]] = i;
}
}
void solve(){
for(int i=1;i<=n;i++) sort(all(qr[i]),[&](pii &a, pii &b){
return a.se < b.se;
});
for(int t= n; t>=1;t--){
for(auto &x: qr[t]){
int r= x.fi, id = x.se;
if(!id){
int k = 2*r-t;
st.update(1,1,n,k,n,a[t]+a[r]);
}
else{
fans[id] = st.get(1,1,n,1,r);
}
}
}
for(int i=1;i<=q;i++) cout<<fans[i]<<"\n";
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
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;
qr[l].pb({r,i});
}
preprocess();
solve();
}
