#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)5e5 + 9;
const int M = (int)1e6 + 10;
vector<int> X[N];
vector<pii> Q[N];
ll A[N];
ll ans[N];
struct Node{
ll sol;
ll f1;
ll f2;
};
Node T[M * 4 + 512];
Node unite(Node A, Node B){
Node res;
res.sol = max(A.sol, B.sol);
res.sol = max(res.sol, A.f1 + B.f2);
res.f1 = max(A.f1, B.f1);
res.f2 = max(A.f2, B.f2);
return res;
}
void upd(int node, int cl, int cr, int pos, ll i1, ll i2){
if(cl == cr){
T[node].f1=max(T[node].f1, i1);
T[node].f2=max(T[node].f2, i2);
T[node].sol=T[node].f1+T[node].f2;
return ;
}
int mid = (cl + cr) / 2;
if(mid >= pos)
upd(node * 2, cl, mid, pos, i1, i2);
else
upd(node * 2 + 1, mid + 1, cr, pos, i1, i2);
T[node] = unite(T[node * 2], T[node * 2 + 1]);
}
Node qq(int node, int cl, int cr, int tl, int tr){
if(cr < tl)
return {0, 0, 0};
if(cl > tr)
return {0, 0, 0};
if(cl >= tl && cr <= tr){
return T[node];
}
int mid = (cl + cr) / 2;
Node f1 = qq(node * 2, cl, mid, tl, tr);
Node f2 = qq(node * 2 + 1, mid + 1, cr, tl, tr);
return unite(f1, f2);
}
int main(){
fastIO;
int n, q;
cin >> n;
vector<int> ids;
for(int i = 1; i <= n; i ++ ){
cin >> A[i];
while(!ids.empty() && A[i] > A[ids.back()]){
X[ids.back()].push_back(i);
ids.pop_back();
}
if(!ids.empty()){
X[ids.back()].push_back(i);
}
ids.push_back(i);
}
cin >> q;
int l, r;
for(int i = 1; i <= q; i ++ ){
cin >> l >>r;
Q[l].push_back(mp(r, i));
}
int id;
for(int r = n; r >= 1; r -- ){
upd(1, 1, n, r, 0ll, A[r]);
for(auto x : X[r]){
id = (2 * x - r);
if(id <= n)
upd(1, 1, n, id, A[r] + A[x], 0ll);
}
for(auto v : Q[r]){
Node qji = qq(1, 1, n, r, v.fi);
ans[v.se] = qji.sol;
}
}
for(int i = 1 ; i <= q; i ++ ){
cout << ans[i] << "\n";
}
return 0;
}
