#include<bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
#define siz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << x << "]"
using namespace std;
bool M1;
const int MAXN = 5e5 + 5, infINT = 1e9 + 13123;
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int numVal, val[MAXN], numQuery, res[MAXN];
vector<int > events[MAXN];
vector<ii > query[MAXN];
struct segmentTree{
int n;
vector<int > lazy, node, mx;
void push(int id, int l, int r){
if (!lazy[id]) return;
if (l != r){
maximize(lazy[id << 1], lazy[id]);
maximize(mx[id << 1], node[id << 1] + lazy[id << 1]);
maximize(lazy[id << 1 | 1], lazy[id]);
maximize(mx[id << 1 | 1], node[id << 1 | 1] + lazy[id << 1 | 1]);
}
lazy[id] = 0;
}
void combine(int id){
node[id] = max(node[id << 1], node[id << 1 | 1]);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}
void build(int id, int l, int r){
if (l > r) return;
if (l == r){
node[id] = val[l];
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
combine(id);
}
segmentTree(int _n = 0): n(_n){
node.assign(n << 2 | 1, 0);
lazy.assign(n << 2 | 1, 0);
mx.assign(n << 2 | 1, 0);
build(1, 1, n);
}
void update(int id, int l, int r, int u, int v, int x){
push(id, l, r);
if (l > r || l > v || r < u || u > v) return;
if (l >= u && r <= v){
maximize(mx[id], node[id] + x);
maximize(lazy[id], x);
push(id, l, r);
return;
}
int m = (l + r) >> 1;
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
combine(id);
}
void update(int u, int v, int x){
update(1, 1, n, u, v, x);
}
int get(int id, int l, int r, int u, int v){
push(id, l, r);
if (l > r || l > v || r < u || u > v) return 0;
if (l >= u && r <= v) return mx[id];
int m = (l + r) >> 1;
return max(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
int get(int u, int v){
return get(1, 1, n, u, v);
}
};
void input(){
cin >> numVal;
for(int i = 1; i <= numVal; i++) cin >> val[i];
cin >> numQuery;
for(int q = 1; q <= numQuery; q++){
int L, R; cin >> L >> R;
query[L].emplace_back(R, q);
}
}
void solve(){
stack<int > st;
for(int i = 1; i <= numVal; i++){
while(siz(st) && val[st.top()] < val[i]) {
events[st.top()].push_back(i);
st.pop();
}
if (siz(st)) events[st.top()].push_back(i);
st.push(i);
}
segmentTree it(numVal);
for(int i = numVal; i >= 1; i--){
for(int j: events[i]){
it.update(j + (j - i), numVal, val[i] + val[j]);
}
for(ii tmp: query[i]){
int j = tmp.fi, id = tmp.se;
res[id] = it.get(i, j);
}
}
for(int id = 1; id <= numQuery; id++){
cout << res[id] << '\n';
}
}
bool M2;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
input();
solve();
cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
cerr << (&M2 - &M1) / 1048576 << " MB\n";
}
