#include<bits/stdc++.h>
#define task "C"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e6 + 5;
const ll INF = 1e18 + 5;
int n, q;
int a[MAXN];
struct TQuery
{
int l, r, id;
};
TQuery qu[MAXN];
void Input()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> q;
for (int i = 1; i <= q; i++)
{
cin >> qu[i].l >> qu[i].r;
qu[i].id = i;
}
}
pair<ll, int> st[4 * MAXN];
ll lazy[4 * MAXN];
pair<ll, int> Comb(const pair<ll, int>& l, const pair<ll, int>& r)
{
return make_pair(max(l.fi, r.fi), max(l.se, r.se));
}
void Build(int id, int l, int r)
{
if (l == r)
{
st[id] = {a[l], a[l]};
return;
}
int mid = (l + r) / 2;
Build(2 * id, l, mid);
Build(2 * id + 1, mid + 1, r);
st[id] = Comb(st[2 * id], st[2 * id + 1]);
}
pair<int, int> seg[MAXN];
int nseg = 0;
void down(int id)
{
ll& t = lazy[id];
if (!t)
return;
st[2 * id].fi = max(st[2 * id].fi, st[2 * id].se + t);
st[2 * id + 1].fi = max(st[2 * id + 1].fi, st[2 * id + 1].se + t);
lazy[2 * id] = max(lazy[2 * id], t);
lazy[2 * id + 1] = max(lazy[2 * id + 1], t);
t = 0;
return;
}
void Update(int id, int l, int r, int u, int v, ll val)
{
if (u > v)
return;
if (r < u || v < l)
return;
if (u <= l && r <= v)
{
st[id].fi = max(st[id].fi, val + st[id].se);
lazy[id] = max(lazy[id], val);
return;
}
down(id);
int mid = (l + r) / 2;
Update(2 * id, l, mid, u, v, val);
Update(2 * id + 1, mid + 1, r, u, v, val);
st[id] = Comb(st[2 * id], st[2 * id + 1]);
}
ll Get(int id, int l, int r, int u, int v)
{
if (r < u || v < l)
return 0;
if (u <= l && r <= v)
{
return st[id].fi;
}
down(id);
int mid = (l + r) / 2;
return max(Get(2 * id, l, mid, u, v), Get(2 * id + 1, mid + 1, r, u, v));
}
int ans[MAXN];
void Solve()
{
Build(1, 1, n);
stack<int> S;
for (int i = n; i >= 1; i--)
{
while (!S.empty() && a[i] > a[S.top()])
{
seg[++nseg] = make_pair(i, S.top());
S.pop();
}
if (!S.empty())
seg[++nseg] = make_pair(i, S.top());
S.push(i);
}
sort(qu + 1, qu + q + 1, [](const auto& i, const auto& j)
{
return i.l > j.l;
});
sort(seg + 1, seg + nseg + 1, [](const auto& i, const auto& j)
{
return i.fi > j.fi;
});
int j = 1;
for (int i = 1; i <= q; i++)
{
while (j <= nseg && seg[j].fi >= qu[i].l)
{
Update(1, 1, n, 2 * seg[j].se - seg[j].fi, n, a[seg[j].se] + a[seg[j].fi]);
j++;
}
ans[qu[i].id] = Get(1, 1, n, qu[i].l, qu[i].r);
}
for (int i = 1; i <= q; i++)
cout << ans[i] << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(task".INP","r"))
{
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
Input();
Solve();
}
