#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 lli pair<long long, int>
#define dbg(x) "[" #x " = " << x << "]"
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
using namespace std;
bool M1;
const long long inf = 1e18 + 123;
const int mod = 1e9 + 7, infINT = 1e9 + 1321, LOG = 10;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
ll ran(ll l, ll r){
return uniform_int_distribution<ll>(l, r)(rd);
}
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
const int MAXN = 5e5 + 5;
int numVal, numQuery, val[MAXN], res[MAXN];
vector<ii > query[MAXN];
vector<int > pos[MAXN];
struct segmentTree{
int n;
vector<int > maxVal, maxTri;
vector<int > lazy;
void build(int id, int l, int r){
if (l > r) return;
if (l == r) return maxTri[id] = maxVal[id] = val[l], void();
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
maxVal[id] = max(maxVal[id << 1], maxVal[id << 1 | 1]);
maxTri[id] = max(maxTri[id << 1], maxTri[id << 1 | 1]);
}
segmentTree(int _n = 0): n(_n){
lazy.assign(n << 2 | 1, -infINT);
maxVal.assign(n << 2 | 1, -infINT);
maxTri.assign(n << 2 | 1, -infINT);
build(1, 1, n);
}
void push(int id, int l, int r){
if (lazy[id] == -infINT) return;
if (l != r){
maximize(maxTri[id << 1], maxVal[id << 1] + lazy[id]);
maximize(maxTri[id << 1 | 1], maxVal[id << 1 | 1] + lazy[id]);
maximize(lazy[id << 1], lazy[id]);
maximize(lazy[id << 1 | 1], lazy[id]);
}
lazy[id] = -infINT;
}
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(lazy[id], x);
maximize(maxTri[id], lazy[id] + maxVal[id]);
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);
maxTri[id] = max(maxTri[id << 1], maxTri[id << 1 | 1]);
}
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 -infINT;
if (l >= u && r <= v) return maxTri[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]){
pos[st.top()].push_back(i);
st.pop();
}
if (siz(st)) pos[st.top()].push_back(i);
st.push(i);
}
segmentTree it(numVal);
it = segmentTree(numVal);
for(int i = numVal; i >= 1; i--){
for(int j: pos[i]){
it.update(j + (j - i), numVal, val[i] + val[j]);
}
for(ii x: query[i]){
int j = x.fi, id = x.se;
res[id] = it.get(i, j);
}
}
for(int q = 1; q <= numQuery; q++) cout << res[q] << '\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 << (&M2 - &M1) / 1048576 << " mb\n";
cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
}
