#include<bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v).size()
template<typename T> bool ckmx(T& a, const T& b){
if(a < b)
return a = b, true;
return false;
}
using ll = long long;
struct SMT{
struct Node{
ll ab, c, best;
Node(ll ab = 0, ll c = 0, ll best = 0): ab(ab), c(c), best(best) {}
friend Node operator + (const Node& x, const Node& y){
Node ans = Node();
ans.ab = max(x.ab, y.ab);
ans.c = max(x.c, y.c);
ans.best = max({x.best, y.best, x.ab + y.c});
return ans;
}
};
int trsz;
vector<Node> st;
SMT(int n = 0): trsz(n), st((n << 2 | 1)) {}
void apply(int id, ll val, int t){
if(!t) ckmx(st[id].ab, val);
else ckmx(st[id].c, val);
st[id].best = st[id].ab + st[id].c;
}
void update(int id, int l, int r, int x, ll val, int t){
if(l == r){
apply(id, val, t);
}
else{
int m = l+r>>1;
if(x <= m)
update(id << 1, l, m, x, val, t);
else update(id << 1|1, m+1, r, x, val, t);
st[id] = st[id << 1] + st[id << 1|1];
}
}
Node get(int id, int l, int r, int u, int v){
if(l >= u && r <= v) return st[id];
int m = l+r>>1;
return (u <= m ? get(id << 1, l, m, u, v) : Node()) +
(v > m ? get(id << 1|1, m+1, r, u, v) : Node());
}
ll query(int l, int r){
return get(1, 1, trsz, l, r).best;
}
void update(int x, ll val, int t){
if(x > trsz) return;
update(1, 1, trsz, x, val, t);
}
};
const int N = 5e5 + 5;
void solve()
{
int n; cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int q; cin >> q;
vector<pair<int,int>> Q(q + 1);
for(int i = 1; i <= q; i++){
cin >> Q[i].first >> Q[i].second;
}
vector<vector<int>> saveQ(n + 1, vector<int>());
for(int i = 1; i <= q; i++){
saveQ[Q[i].first].push_back(i);
}
SMT st(n); stack<int> candidate;
auto update_candidate = [&](int i, int j) -> void{
ll value = 1ll * a[i] + 1ll * a[j];
// (j - i) <= (k - j) -> k >= j + (j - i)
int k = j + (j - i);
st.update(k, value, 0);
};
vector<ll> answer(q + 1);
/*
if a[i] < a[st.top()] it's just useless to update it more
(a[st.top()] with a[st.top() - 1] can give better answer) (more jumping range, more firmness)
it can only contribute to position that i -> st.top() can contribute
*/
for(int i = n; i >= 1; i--){
st.update(i, a[i], 1);
while(!candidate.empty() && a[i] >= a[candidate.top()]){
update_candidate(i, candidate.top());
candidate.pop();
}
if(!candidate.empty()){
update_candidate(i, candidate.top());
}
candidate.push(i);
for(int id : saveQ[i]){
int r = Q[id].second;
answer[id] = st.query(i, r);
}
}
for(int i = 1; i <= q; i++){
cout << answer[i] << "\n";
}
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "InvMOD"
if(fopen(name".INP", "r")){
freopen(name".INP", "r", stdin);
freopen(name".OUT", "w", stdout);
}
solve();
return 0;
}
