#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T>
void read(T &x)
{
x = 0;
register int c;
while ((c = getchar()) && (c > '9' || c < '0'))
;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
}
constexpr bool typetest = 0;
constexpr int N = 5e5 + 5;
constexpr ll Inf = 1e17;
struct SegmentTree
{
int n;
ll lazy[N * 4], st[N * 4], maxn[N * 4];
SegmentTree()
{
fill_n(lazy, N * 4, -Inf);
fill_n(st, N * 4, -Inf);
fill_n(maxn, N * 4, -Inf);
}
void Build(int id, int l, int r, ll a[N])
{
if (l == r)
{
maxn[id] = a[l];
return;
}
Build(id << 1, l, (l + r) / 2, a);
Build(id << 1 | 1, (l + r) / 2 + 1, r, a);
maxn[id] = max(maxn[id << 1], maxn[id << 1 | 1]);
}
void Build(ll a[N])
{
Build(1, 1, n, a);
}
void Push(int id)
{
if (lazy[id] != -Inf)
{
if (lazy[id << 1] < lazy[id])
{
lazy[id << 1] = lazy[id];
st[id << 1] = max(st[id << 1], maxn[id << 1] + lazy[id]);
}
if (lazy[id << 1 | 1] < lazy[id])
{
lazy[id << 1 | 1] = lazy[id];
st[id << 1 | 1] = max(st[id << 1 | 1], maxn[id << 1 | 1] + lazy[id]);
}
lazy[id] = -Inf;
}
}
void Update(int id, int l, int r, const int &a, const int &b, const ll &v)
{
if (l > b || r < a)
return;
if (l >= a && r <= b)
{
if (lazy[id] < v)
{
lazy[id] = v;
st[id] = max(st[id], maxn[id] + v);
}
return;
}
Push(id);
Update(id << 1, l, (l + r) / 2, a, b, v);
Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
void Update(int l, int r, ll v)
{
Update(1, 1, n, l, r, v);
}
ll Get(int id, int l, int r, const int &a, const int &b)
{
if (l > b || r < a)
return -Inf;
if (l >= a && r <= b)
return st[id];
Push(id);
return max(Get(id << 1, l, (l + r) / 2, a, b), Get(id << 1 | 1, (l + r) / 2 + 1, r, a, b));
}
ll Get(int l, int r)
{
return Get(1, 1, n, l, r);
}
} f;
int n, q, m;
ll a[N], ans[N];
struct Query
{
int l, r, id;
bool operator<(const Query &a) const
{
return l > a.l || (l == a.l && r > a.r);
}
} s[N], p[N * 2];
void Read()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
cin >> q;
for (int i = 1; i <= q; ++i)
cin >> s[s[i].id = i].l >> s[i].r;
}
void Solve()
{
f.n = n;
f.Build(a);
vector<int> tmp;
for (int i = 1; i <= n; ++i)
{
while (!tmp.empty() && a[tmp.back()] < a[i])
tmp.pop_back();
if (!tmp.empty())
{
++m;
p[m].l = tmp.back();
p[m].r = i;
}
tmp.emplace_back(i);
}
tmp.clear();
for (int i = n; i; --i)
{
while (!tmp.empty() && a[tmp.back()] < a[i])
tmp.pop_back();
if (!tmp.empty())
{
++m;
p[m].r = tmp.back();
p[m].l = i;
}
tmp.emplace_back(i);
}
sort(s + 1, s + q + 1);
sort(p + 1, p + m + 1);
for (int i = 1, j = 1; i <= q; ++i)
{
while (j <= m && p[j].l >= s[i].l)
{
f.Update(p[j].r + (p[j].r - p[j].l), n, a[p[j].l] + a[p[j].r]);
++j;
}
ans[s[i].id] = f.Get(s[i].l, s[i].r);
}
for (int i = 1; i <= q; ++i)
cout << ans[i] << "\n";
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t(1);
if (typetest)
cin >> t;
for (int _ = 1; _ <= t; ++_)
{
//cout << "Case #" << _ << ": ";
Read();
Solve();
}
//cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
