#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
template<typename T> struct segtree {
T merge(T x, T y) {
return max(x, y);
}
int n;
vector<ll> t;
void init(int n) {
n += 10;
this->n = n;
t.resize(n*4);
}
void upd(int v, int tl, int tr, int i, T dx) {
if (tl == tr) {
t[v] = merge(t[v], dx);
} else {
int tm = (tl+tr)/2;
if (i<=tm) {
upd(2*v,tl,tm,i,dx);
} else {
upd(2*v+1,tm+1,tr,i,dx);
}
t[v] = merge(t[2*v], t[2*v+1]);
}
}
T qry(int v, int tl, int tr, int l, int r) {
if (l>tr || r<tl) {
return 0;
}
if (l <= tl && tr <= r) {
return t[v];
}
int tm = (tl+tr)/2;
return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
}
};
struct sparse_table {
//0-indexed, init with vector.
//todo: call init()
const static int LOG = 18; //todo
int n;
vector<int> a[LOG+1];
vector<int> lg_floor;
//todo
int eval(int x, int y) {
return max(x, y);
}
//todo: ll vs int
void init(vector<int> v) {
n = v.size();
lg_floor.resize(n+10);
lg_floor[1] = 0;
for (int i=2; i<n+10; i++) lg_floor[i] = 1 + lg_floor[i/2];
for (int j=0; j<LOG; j++) a[j].resize(n);
for (int i=0; i<n; i++) a[0][i] = v[i];
for (int j=1; j<LOG; j++) {
for (int i=0; i<n; i++) {
a[j][i] = a[j-1][i];
if (i + (1<<(j-1)) < n) {
a[j][i] = eval(a[j][i], a[j-1][i + (1<<(j-1))]);
}
}
}
}
int get(int l, int r) {
assert(l<=r);
int lg = lg_floor[r - l + 1];
return eval(a[lg][l], a[lg][r-(1<<lg)+1]);
}
};
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
int n, q;
int A[maxn];
vector<pair<int,int>> Q;
int ans[maxn];
vector<int> ev[maxn];
sparse_table st;
segtree<int> sg;
void init_st() {
vector<int> a;
for (int i=1; i<=n; i++) {
a.push_back(A[i]);
}
st.init(a);
}
int qryMax(int l, int r) {
assert(l<=r);
return st.get(l-1,r-1);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1; i<=n; i++) {
cin>>A[i];
}
init_st();
sg.init(n+10);
cin>>q;
Q.resize(q);
for (int i=0; i<q; i++) {
cin>>Q[i].first>>Q[i].second;
ev[Q[i].second].push_back(i);
}
for (int r=3; r<=n; r++) {
for (int l=1; l<=r-2; l++) {
int mid = (l+r)/2;
int mx = qryMax(l+1,mid);
sg.upd(1,1,n,l,mx+A[l]+A[r]);
}
for (int idx: ev[r]) {
int L = Q[idx].first; int R = Q[idx].second;
ans[idx] = max(ans[idx], sg.qry(1,1,n,L,R));
}
}
for (int i=0; i<q; i++) {
cout<<ans[i]<<"\n";
}
return 0;
}
