#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = (1 << 20) + 1;
const int INF = -1e18;
int iDeb[MAXN], iFin[MAXN], lazyMax[MAXN], maxVal[MAXN], strengh[MAXN],
maxStrength[MAXN];
void buildTree(int iNoeud, int deb, int fin) {
iDeb[iNoeud] = deb, iFin[iNoeud] = fin;
lazyMax[iNoeud] = INF;
if (deb == fin) {
maxStrength[iNoeud] = strengh[deb];
maxVal[iNoeud] = INF;
return;
}
buildTree(2 * iNoeud, deb, (deb + fin) / 2);
buildTree(2 * iNoeud + 1, (deb + fin) / 2 + 1, fin);
maxVal[iNoeud] = INF;
maxStrength[iNoeud] =
max(maxStrength[2 * iNoeud], maxStrength[2 * iNoeud + 1]);
}
void push(int iNoeud) {
if (lazyMax[iNoeud] == INF)
return;
maxVal[iNoeud] = max(maxVal[iNoeud], maxStrength[iNoeud] + lazyMax[iNoeud]);
if (iDeb[iNoeud] < iFin[iNoeud]) {
lazyMax[iNoeud * 2] = max(lazyMax[2 * iNoeud], lazyMax[iNoeud]);
lazyMax[1 + iNoeud * 2] = max(lazyMax[2 * iNoeud], lazyMax[iNoeud]);
}
lazyMax[iNoeud] = INF;
}
void upd(int iNoeud, int deb, int fin, int v) {
push(iNoeud);
if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
return;
if (iDeb[iNoeud] >= deb and iFin[iNoeud] <= fin) {
lazyMax[iNoeud] = v;
push(iNoeud);
return;
}
upd(2 * iNoeud, deb, fin, v);
upd(1 + 2 * iNoeud, deb, fin, v);
maxVal[iNoeud] = max(maxVal[2 * iNoeud], maxVal[2 * iNoeud + 1]);
}
int query(int iNoeud, int deb, int fin) {
push(iNoeud);
if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
return INF;
if (iDeb[iNoeud] >= deb and iFin[iNoeud] <= fin)
return maxVal[iNoeud];
return max(query(2 * iNoeud, deb, fin), query(2 * iNoeud + 1, deb, fin));
}
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i < N; ++i)
cin >> strengh[i];
vector<vector<int>> interessants(N);
vector<pair<int, int>> curRecords;
for (int b = 1; b < N; ++b) {
while (!curRecords.empty() and curRecords.back().first <= strengh[b - 1])
curRecords.pop_back();
curRecords.emplace_back(strengh[b - 1], b - 1);
for (int i = (int)curRecords.size() - 1; i >= 0; --i) {
auto [val, pos] = curRecords[i];
if (b - pos + b < N)
interessants[pos].push_back(b);
if (val >= strengh[b])
break;
}
}
int Q;
cin >> Q;
vector<vector<pair<int, int>>> queries(N);
vector<int> ret(Q);
for (int i = 0; i < Q; ++i) {
int l, r;
cin >> l >> r;
--l, --r;
queries[l].emplace_back(r, i);
}
buildTree(1, 0, N - 1);
for (int a = N - 1; a >= 0; --a) {
for (int b : interessants[a]) {
if (b + b - a < N)
upd(1, 2 * b - a, N - 1, strengh[a] + strengh[b]);
}
for (auto [r, id] : queries[a])
ret[id] = query(1, a + 2, r);
}
for (auto v : ret)
cout << v << '\n';
}
