#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, K, Q;
int A[500001];
struct Query
{
int l, r, i;
const bool operator < (const Query &q) const {return l < q.l;}
}QR[500001];
struct Node
{
ll max0, max1, mind, maxd, p;
}ST[2000001];
vector <pair <int, int>> V;
ll O[500001];
inline void Merge(int i)
{
if(i >= K) return;
ST[i].mind = min(ST[i << 1].mind, ST[i << 1 | 1].mind);
ST[i].maxd = max(ST[i << 1].maxd, ST[i << 1 | 1].maxd);
ST[i].max1 = max(ST[i << 1].max1, ST[i << 1 | 1].max1);
return;
}
inline void Propagate(int i)
{
if(!ST[i].p) return;
ST[i].max1 = ST[i].max0 + (ST[i].mind = ST[i].maxd = ST[i].p);
if(i < K) ST[i << 1].p = ST[i << 1 | 1].p = ST[i].p;
ST[i].p = 0;
return;
}
inline void Setup()
{
K = 1;
while(K < N) K <<= 1;
for(int i = 1; i <= N; i++) ST[i + K - 1] = {A[i], 0, 0, 0, 0};
for(int i = K - 1; i; i--) ST[i].max0 = max(ST[i << 1].max0, ST[i << 1 | 1].max0);
for(int i = K - 1; i; i--) Merge(i);
return;
}
inline void Update(int l, int r, ll x, int i = 1, int lc = 1, int rc = K)
{
Propagate(i);
if((lc > r) || (l > rc)) return;
if((l <= lc) && (rc <= r) && (ST[i].mind >= x)) return;
if((l <= lc) && (rc <= r) && (ST[i].mind == ST[i].maxd)) {ST[i].p = x; return Propagate(i);}
int s = (lc + rc) >> 1;
Update(l, r, x, i << 1, lc, s);
Update(l, r, x, i << 1 | 1, s + 1, rc);
Merge(i);
return;
}
inline ll Get(int l, int r, int i = 1, int lc = 1, int rc = K)
{
Propagate(i);
if((lc > r) || (l > rc)) return 0;
if((l <= lc) && (rc <= r)) return ST[i].max1;
int s = (lc + rc) >> 1;
ll ret = max(Get(l, r, i << 1, lc, s), Get(l, r, i << 1 | 1, s + 1, rc));
Merge(i);
return ret;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N;
for(int i = 1; i <= N; i++) cin >> A[i];
Setup();
stack <pair <int, int>> S;
for(int i = 1; i <= N; i++)
{
while(S.size() && (S.top().first < A[i])) S.pop();
if(S.size()) V.push_back({S.top().second, i});
S.push({A[i], i});
}
while(S.size()) S.pop();
for(int i = N; i >= 1; i--)
{
while(S.size() && (S.top().first < A[i])) S.pop();
if(S.size()) V.push_back({i, S.top().second});
S.push({A[i], i});
}
sort(V.begin(), V.end());
cin >> Q;
for(int i = 1; i <= Q; i++) {cin >> QR[i].l >> QR[i].r; QR[i].i = i;}
sort(QR + 1, QR + Q + 1);
for(int i = Q, j = V.size() - 1, l = N + 1; i >= 1; i--)
{
while((j >= 0) && (V[j].first >= QR[i].l))
{
if(((V[j].second << 1) - V[j].first) <= N)
{
Update((V[j].second << 1) - V[j].first, N, A[V[j].first] + A[V[j].second]);
l = min((V[j].second << 1) - V[j].first, l);
}
j--;
}
O[QR[i].i] = Get(max(l, QR[i].l), QR[i].r);
}
for(int i = 1; i <= Q; i++) cout << O[i] << " \n"[i == Q];
return 0;
}
