#include <bits/stdc++.h>
using namespace std;
#define file if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
// #define int long long
#define f first
#define s second
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
if (s.size()) setIn(s+".inp"), setOut(s+".out");
}
const int maxn = 5e5 + 2;
int a[maxn], n, q;
namespace Sub1
{
void solve()
{
while (q--)
{
int l, r, ans = 0;
cin >> l >> r;
for (int i = l; i <= r; i++)
{
for (int j = i + 1; j <= r; j++)
{
for (int k = j + 1; k <= r; k++)
{
if (k - j >= j - i)
{
ans = max(ans, a[i] + a[j] + a[k]);
}
}
}
}
cout << ans << '\n';
}
}
} // namespace Sub1
namespace Sub2
{
const int s2maxn = 5002;
int dp[s2maxn][s2maxn], mx[s2maxn][s2maxn];
void solve()
{
for (int i = 1; i <= n; i++)
{
mx[i][i] = a[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
mx[i][j] = max(mx[i][j - 1], a[j]);
}
}
for (int sz = 3; sz <= n; sz++)
{
for (int i = 1; i + sz - 1 <= n; i++)
{
int l = i, r = i + sz - 1;
// if (sz == 3 && i == 1)
// cout << l << ' ' << r << ' ' << (l + r) / 2 << ' ' << mx[l][(l + r) / 2] << '\n';
dp[l][r] = max({dp[l + 1][r], dp[l][r - 1], a[l] + a[r] + mx[l + 1][(l + r) / 2]});
}
}
while (q--)
{
int l, r;
cin >> l >> r;
cout << dp[l][r] << '\n';
}
}
} // namespace Sub2
namespace Sub3
{
int prf[maxn];
void solve()
{
stack <int> st;
for (int i = 1; i <= n; i++)
{
while (st.size() && a[st.top()] < a[i])
{
if (i + (i - st.top() + 1) - 1 <= n)
prf[i + i - st.top()] = max(prf[i + i - st.top()], a[i] + a[st.top()]);
st.pop();
}
if (st.size())
if (i + (i - st.top() + 1) - 1 <= n)
prf[i + i - st.top()] = max(prf[i + i - st.top()], a[i] + a[st.top()]);
st.push(i);
}
for (int i = 1; i <= n; i++)
{
prf[i] = max(prf[i - 1], prf[i]);
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans = max(ans, prf[i] + a[i]);
}
cout << ans << '\n';
}
} // namespace Sub3
namespace Sub4
{
struct node
{
int cur, mx, v;
};
node tree[maxn * 4];
void build(int id, int l, int r)
{
if (l == r)
{
tree[id].cur = a[l];
tree[id].v = a[l];
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
tree[id].v = max({tree[id * 2].v, tree[id * 2 + 1].v, tree[id * 2].mx + tree[id * 2 + 1].cur});
tree[id].cur = max(tree[id * 2].cur, tree[id * 2 + 1].cur);
}
// void push(int id)
// {
// int tmp = tree[id].mx ;
// tree[id * 2].mx = max(tmp, tree[id * 2].mx);
// tree[id * 2 + 1].mx = max(tmp, tree[id * 2 + 1].mx);
// tree[id * 2].v = max(tmp + tree[id * 2].cur, tree[id * 2].v);
// tree[id * 2 + 1].v = max(tmp + tree[id * 2 + 1].cur, tree[id * 2 + 1].v);
// }
node merge(node l, node r)
{
return {max(l.cur, r.cur), max(l.mx, r.mx), max({l.v, l.mx + r.cur, r.v})};
}
void update(int id, int l, int r, int u, int v, int vl)
{
if (r < u || v < l)
return;
if (l >= u && r <= v)
{
tree[id].mx = max(tree[id].mx, vl);
tree[id].v = max(tree[id].cur + tree[id].mx, tree[id].v);
return;
}
// push(id);
int mid = (l + r) / 2;
update(id * 2, l, mid, u, v, vl);
update(id * 2 + 1, mid + 1, r, u, v, vl);
tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}
node get(int id, int l, int r, int u, int v)
{
if(r < u || v < l)
return {0, 0, 0};
if (l >= u && r <= v)
{
// cout << l << ' ' << r << ' ' << tree[id].v << '\n';
return tree[id];
}
// push(id);
int mid = (l + r) / 2;
return merge(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
vector <pair <int, int>> Q[maxn];
int ans[maxn];
void solve()
{
for (int i = 1; i <= q; i++)
{
int l, r;
cin >> l >> r;
Q[l].push_back({r, i});
}
build(1, 1, n);
stack <int> st;
for (int i = n; i >= 1; i--)
{
while (st.size() && a[st.top()] < a[i])
{
if (-i + 2 * st.top() <= n)
update(1, 1, n, -i + 2 * st.top(), -i + 2 * st.top(), a[i] + a[st.top()]);
st.pop();
}
if (st.size())
if (-i + 2 * st.top() <= n)
update(1, 1, n, -i + 2 * st.top(), -i + 2 * st.top(), a[i] + a[st.top()]);
st.push(i);
for (auto [r, id] : Q[i])
{
ans[id] = get(1, 1, n, i, r).v;
// cout << " -> " << id << ' ' << ans[id] << '\n';
}
}
// cout << tree[1].v << '\n';
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
}
} // namespace Sub4
signed main()
{
// setIO();
file;
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> q;
if (n <= 100)
{
return Sub1::solve(), 0;
}
if (n <= 5000)
{
return Sub2::solve(), 0;
}
if (q == 1)
{
return Sub3::solve(), 0;
}
return Sub4::solve(), 0;
}
