#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int , int>
const int N = 5e5 + 5;
pii st[4 * N];
int stadd[4 * N];
int a[N];
int res[N];
vector<pii> queries[N];
int n , q;
bool cmp(const pii& x, const pii& y){
return x.second < y.second;
}
void build(int idx , int l , int r){
if(l == r){
st[idx].first = a[l];
st[idx].second = a[l];
return;
}
int mid = (l + r) / 2;
build(2 * idx , l , mid);
build(2 * idx + 1 , mid + 1 , r);
st[idx].first = max(st[2 * idx].first , st[2 * idx + 1].first);
st[idx].second = st[idx].first;
}
void update(int idx , int l , int r , int u , int v , int val){
if(l > v || r < u) return;
if(u <= l && r <= v){
stadd[idx] = max(stadd[idx] , val);
st[idx].second = max(st[idx].second , st[idx].first + val);
return;
}
int mid = (l + r) / 2;
update(2 * idx , l , mid , u , v, val);
update(2 * idx + 1 , mid + 1 , r , u , v , val);
st[idx].second = max({st[2 * idx].second , st[2 * idx + 1].second , st[idx].first + stadd[idx]});
}
pii get(int idx , int l , int r , int u , int v){
if(l > v || r < u) return {0 , 0};
if(u <= l && r <= v) return st[idx];
int mid = (l + r) / 2;
pii t1 = get(2 * idx , l , mid , u , v);
pii t2 = get(2 * idx + 1 , mid + 1 , r , u , v);
return make_pair(max(t1.first , t2.first) , max({t1.second , t2.second , max(t1.first, t2.first) + stadd[idx]}));
}
void upd(int l , int r){
int pos = r * 2 - l;
if(pos > n) return;
update(1 , 1 , n , pos , n , a[l] + a[r]);
}
void emconhoanhko(void){
stack<int> s;
for(int i = n ; i >= 1 ; i--){
while(s.size() && a[i] >= a[s.top()]){
upd(i , s.top());
s.pop();
}
if(s.size()) upd(i , s.top());
s.push(i);
for(auto x : queries[i]) res[x.second] = get(1 , 1 , n , i , x.first).second;
}
}
void solve(void){
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;
queries[l].push_back({r , i});
}
build(1 , 1 , n);
emconhoanhko();
for(int i = 1 ; i <= q ; i++) cout << res[i] << endl;
}
signed main(void){
ios_base :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
solve();
return 0;
}
