#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask , x) (((mask)>>x)&(1))
#define sz(x) (int)(x).size()
template<class X,class Y>
bool maximize(X &x , Y y){
if (x < y) return x = y , true; else return false;
}
template<class X,class Y>
bool minimize(X &x , Y y){
if (x > y) return x = y , true; else return false;
}
template<class T>
void compress(vector<T>&data){
sort(data.begin() , data.end());
data.resize(unique(data.begin() , data.end()) - data.begin());
}
template<class X,class Y>
int Find(vector<X>&data,Y y){
return upper_bound(data.begin() , data.end() , y) - data.begin();
}
const int N = (int) 5e5;
int a[N + 2] , ans[N + 2];
int n , q;
vector<pair<int,int>>block[N+2];
vector<pair<int,int>>add[N+2];
void insert_block(int l, int r){
add[l].push_back({2 * r - l , a[l] + a[r]});
return;
}
LL st_val[N*4+2] , st_upd[N*4+2] , st[N*4+2];
void reup(int id){
maximize(st[id] , st_val[id] + st_upd[id]);
return;
}
void build(int id,int l,int r){
if (l==r) st_val[id] = st[id] = a[l];
else{
int m = (l + r) / 2;
build(id*2,l,m);
build(id*2+1,m+1,r);
st_val[id] = max(st_val[id*2] , st_val[id*2+1]);
reup(id);
}
return;
}
void pushdown(int id){
LL &t = st_upd[id];
maximize(st_upd[id*2],t);
maximize(st_upd[id*2+1],t);
reup(id*2) , reup(id*2+1);
return;
}
void upd(int id , int l, int r , int u , int v ,LL val){
if (l > v || r < u) return;
if (u <= l && r <= v) {
maximize(st_upd[id] , val);
reup(id);
return;
}
int m = (l + r)/2;
pushdown(id);
upd(id*2,l,m,u,v,val);
upd(id*2+1,m+1,r,u,v,val);
st[id] = max(st[id*2] , st[id*2+1]);
}
LL Get(int id , int l, int r , int u , int v){
if (l > v || r < u) return 0;
if (u <= l && r <= v) {
reup(id);
return st[id];
}
int m = (l+r)/2;
pushdown(id);
return max(Get(id*2,l,m,u,v) , Get(id*2+1,m+1,r,u,v));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0) ;
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".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;
block[l].push_back({r , i});
}
vector<int>st;
for(int i = n; i >= 1; --i){
while (st.size() && a[st.back()] <= a[i]){
insert_block(i , st.back());
st.pop_back();
}
if (st.size()) insert_block(i , st.back());
st.push_back(i);
}
build(1,1,n);
for(int i = n; i >= 1; --i){
for(auto& x : add[i]) upd(1,1,n,x.first,n,x.second);
for(auto& x : block[i]) ans[x.second] = Get(1,1,n,i,x.first);
}
for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}
