#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <utility>
class Interval
{
int left, right;
public:
Interval(int l, int r) : left(l), right(r) {}
bool IsIncludedIn(const Interval &other) const
{
return (other.left <= left && right <= other.right);
}
bool IsDisjointFrom(const Interval &other) const
{
return (other.right <= left || right <= other.left);
}
Interval Left() const
{
return Interval(left, (left + right) / 2);
}
Interval Right() const
{
return Interval((left + right) / 2, right);
}
};
const int MAXN = 5e5;
const int LEAVES = 1 << 19;
const int TSIZE = LEAVES << 1;
const Interval ROOTCOVER = { 0, LEAVES };
int firmness[MAXN];
std::stack<int> useful;
std::vector<std::pair<int, int>> seg[MAXN];
std::vector<std::pair<int, int>> query[MAXN];
int maxFirm[TSIZE];
int bestScore[TSIZE], lazy[TSIZE];
int answer[MAXN];
void createusefulsegments(int positions)
{
for (int iPos = 0; iPos < positions; iPos++)
{
while (!useful.empty() && firmness[useful.top()] < firmness[iPos])
{
seg[useful.top()].emplace_back(2 * iPos - useful.top(), firmness[iPos] + firmness[useful.top()]);
useful.pop();
}
if (!useful.empty())
seg[useful.top()].emplace_back(2 * iPos - useful.top(), firmness[iPos] + firmness[useful.top()]);
useful.emplace(iPos);
}
}
void setup(int positions)
{
for (int iPos = 0; iPos < positions; iPos++)
maxFirm[iPos + LEAVES] = firmness[iPos];
for (int iNode = LEAVES - 1; iNode > 0; iNode--)
maxFirm[iNode] = std::max(maxFirm[iNode * 2], maxFirm[iNode * 2 + 1]);
}
void push(int node)
{
bestScore[node] = std::max(bestScore[node], maxFirm[node] + lazy[node]);
if (node < LEAVES)
{
lazy[node * 2] = std::max(lazy[node * 2], lazy[node]);
lazy[node * 2 + 1] = std::max(lazy[node * 2 + 1], lazy[node]);
}
}
void update(int node, Interval covered, Interval requested, int value)
{
push(node);
if (covered.IsIncludedIn(requested))
{
lazy[node] = std::max(lazy[node], value);
push(node);
}
else if (!covered.IsDisjointFrom(requested))
{
update(node * 2, covered.Left(), requested, value);
update(node * 2 + 1, covered.Right(), requested, value);
bestScore[node] = std::max(bestScore[node], std::max(bestScore[node * 2], bestScore[node * 2 + 1]));
}
}
int request(int node, Interval covered, Interval requested)
{
push(node);
if (covered.IsIncludedIn(requested))
return bestScore[node];
if (covered.IsDisjointFrom(requested))
return 0;
return std::max(request(node * 2, covered.Left(), requested), request(node * 2 + 1, covered.Right(), requested));
}
int main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
int positions; std::cin >> positions;
for (int iPos = 0; iPos < positions; iPos++)
std::cin >> firmness[iPos];
createusefulsegments(positions);
setup(positions);
int queries; std::cin >> queries;
for (int iQuery = 0; iQuery < queries; iQuery++)
{
int left, right;
std::cin >> left >> right;
query[left - 1].emplace_back(iQuery, right);
}
for (int iPos = positions - 1; iPos > -1; iPos--)
{
for (std::pair<int, int> &add : seg[iPos])
if (add.first < positions)
update(1, ROOTCOVER, Interval(add.first, positions), add.second);
for (std::pair<int, int> &ask : query[iPos])
answer[ask.first] = request(1, ROOTCOVER, Interval(iPos, ask.second));
}
for (int iQuery = 0; iQuery < queries; iQuery++)
std::cout << answer[iQuery] << '\n';
return 0;
}
