#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;
const int N = 5e5 + 2;
const int INF = 1e9;
struct segmentTree{
int n, maxVal[N * 4], lazy[N * 4], maxA[N * 4];
void build(int id, int l, int r, int a[N]){
if (l == r){
maxVal[id] = maxA[id] = a[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid, a);
build(id << 1 | 1, mid + 1, r, a);
maxVal[id] = max(maxVal[id << 1], maxVal[id << 1 | 1]);
maxA[id] = max(maxA[id << 1], maxA[id << 1 | 1]);
}
void doLazy(int id, int l, int r){
maxVal[id] = max(maxVal[id], lazy[id] + maxA[id]);
if (l < r){
lazy[id << 1] = max(lazy[id << 1], lazy[id]);
lazy[id << 1 | 1] = max(lazy[id << 1 | 1], lazy[id]);
}
}
void update(int id, int l, int r, int u, int v, int val){
doLazy(id, l, r);
if (v < l || r < u)
return;
if (u <= l && r <= v){
lazy[id] = max(lazy[id], val);
doLazy(id, l, r);
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
maxVal[id] = max(maxVal[id << 1], maxVal[id << 1 | 1]);
}
int getMax(int id, int l, int r, int u, int v){
doLazy(id, l, r);
if (v < l || r < u)
return 0;
if (u <= l && r <= v)
return maxVal[id];
int mid = (l + r) >> 1;
return max(getMax(id << 1, l, mid, u, v), getMax(id << 1 | 1, mid + 1, r, u, v));
}
void init(int _n, int a[N]){
assert(_n > 0);
n = _n;
build(1, 1, n, a);
}
void update(int l, int r, int val){
assert(1 <= l && l <= r && r <= n);
update(1, 1, n, l, r, val);
}
int getMax(int l, int r){
assert(1 <= l && l <= r && r <= n);
return getMax(1, 1, n, l, r);
}
} ST;
int n, q, a[N], answer[N];
vector <int> imp[N];
vector <ii> query[N];
void readInput(){
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;
query[l].push_back(mp(r, i));
}
}
void solve(){
stack <int> st;
a[n + 1] = INF;
st.push(n + 1);
for(int i = n; i >= 1; i--){
while (a[i] > a[st.top()]){
imp[i].push_back(st.top());
st.pop();
}
if (st.top() != n + 1)
imp[i].push_back(st.top());
st.push(i);
}
ST.init(n, a);
for(int l = n; l >= 1; l--){
for(int r : imp[l]){
int k = 2 * r - l;
if (k <= n)
ST.update(k, n, a[l] + a[r]);
}
for(ii qr : query[l]){
int r = qr.X;
int ind = qr.Y;
answer[ind] = ST.getMax(l, r);
}
}
for(int i = 1; i <= q; i++)
cout << answer[i] << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
readInput();
solve();
return 0;
}
