#include <bits/stdc++.h>
#define int long long
using namespace std;
int N,Q,A[500000],L,R,ANS[500000];
int S1[2000000],S2[2000000],S3[2000000];
vector<pair<int,int>>PA[500000];
int seg[2000000];
/*void upd2(int T,int v,int LL=0,int RR=500000,int idx=0){
if(LL == RR && LL == T){seg[idx] = max(seg[idx],v);return;}
else if(LL > T || RR < T)return;
upd2(T,v,LL,(LL+RR)/2,idx*2+1),upd2(T,v,(LL+RR)/2+1,RR,idx*2+2);
}
int query2(int L,int R,int LL=0,int RR=500000,int idx=0){
if(LL >= L && RR <= R)return seg[idx];
else if(LL > R || RR < L) return 0;
return max(query2(L,R,LL,(LL+RR)/2,idx*2+1),query2(L,R,(LL+RR)/2+1,RR,idx*2+2));
}*/
void upd(int T,int v,int LL = 0,int RR = 500000,int idx = 0){
if(LL == RR && LL == T){
S1[idx] = max(v,S1[idx]);
S2[idx] = A[T];
S3[idx] = S1[idx] + A[T];
return;
}
else if(LL > T || RR < T)return;
upd(T,v,LL,(LL+RR)/2,idx*2+1),upd(T,v,(LL+RR)/2+1,RR,idx*2+2);
S3[idx] = max({S3[idx*2+1],S3[idx*2+2],S1[idx*2+1] + S2[idx*2+2]});
S1[idx] = max(S1[idx*2+1],S1[idx*2+2]);
S2[idx] = max(S2[idx*2+1],S2[idx*2+2]);
}
pair<pair<int,int>,int>query(int L,int R,int LL=0,int RR=500000,int idx=0){
if(RR <= R && LL >= L){
return {{S3[idx],S1[idx]},S2[idx]};
}
else if(LL > R || RR < L)return {{(int)-3e8,0},0};
pair<pair<int,int>,int>F1 = query(L,R,LL,(LL+RR)/2,idx*2+1);
pair<pair<int,int>,int>F2 = query(L,R,(LL+RR)/2+1,RR,idx*2+2);
F1.first.first = max({F1.first.first,F2.first.first,F1.first.second + F2.second});
F1.first.second = max(F1.first.second,F2.first.second);
F1.second = max(F1.second,F2.second);
return F1;
}
void CALC(){
stack<pair<int,int>>F;
for(int i = 0; i < N; i += 1){
while(F.size()){
pair<int,int>TOP = F.top();
PA[TOP.second].push_back({i, i * 2 - TOP.second});
if(TOP.first > A[i])break;
F.pop();
}
F.push({A[i],i});
}
}
int32_t main()
{
cin.tie(0),iostream::sync_with_stdio(0);
cin>>N;
for(int i = 0; i < N; i += 1){
cin>>A[i];
upd(i,0);
}
CALC();
cin>>Q;
vector<array<int,3>>STO;
for(int i = 0; i < Q; i += 1){
cin>>L>>R,L--,R--;
STO.push_back({L,R,i});
}
int LST = N;
sort(STO.rbegin(),STO.rend());
for(int i = 0; i < Q; i += 1){
while(LST > STO[i][0]){
LST--;
for(int l = 0; l < PA[LST].size();l++){
upd(PA[LST][l].second,A[PA[LST][l].first] + A[LST]);
}
}
//cout<<STO[i][1]<<endl;
ANS[STO[i][2]] = query(STO[i][0],STO[i][1]).first.first;
}
for(int i = 0; i < Q; i += 1)cout<<ANS[i]<<'\n';
}
