#include <bits/stdc++.h>
using namespace std;
void setup()
{
#ifndef ONLINE_JUDGE
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, a[500001], q, b, c, res[500000];
vector<int> v;
vector<pair<int, int>> query[500001];
struct SEGMENT_TREE
{
int tree[2000000], rem[2000000], base[2000000];
inline void Build(int ind, int l, int r)
{
if (l == r)
{
base[ind] = a[l];
return;
}
int m = (l + r) >> 1;
Build(ind << 1, l, m);
Build(ind << 1 | 1, m + 1, r);
base[ind] = max(base[ind << 1], base[ind << 1 | 1]);
}
inline void Update(int ind, int l, int r, int x, int y, int v)
{
tree[ind] = max(tree[ind], base[ind] + rem[ind]);
if (r < x || y < l)
{
return;
}
if (x <= l && r <= y)
{
rem[ind] = max(rem[ind], v);
tree[ind] = max(tree[ind], base[ind] + rem[ind]);
return;
}
rem[ind << 1] = max(rem[ind], rem[ind << 1]);
rem[ind << 1 | 1] = max(rem[ind], rem[ind << 1 | 1]);
int m = (l + r) >> 1;
Update(ind << 1, l, m, x, y, v);
Update(ind << 1 | 1, m + 1, r, x, y, v);
tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]);
}
inline int Get(int ind, int l, int r, int x, int y)
{
tree[ind] = max(tree[ind], base[ind] + rem[ind]);
if (y < l || r < x)
{
return 0;
}
if (x <= l && r <= y)
{
return tree[ind];
}
rem[ind << 1] = max(rem[ind], rem[ind << 1]);
rem[ind << 1 | 1] = max(rem[ind], rem[ind << 1 | 1]);
int m = (l + r) >> 1;
return max(Get(ind << 1, l, m, x, y), Get(ind << 1 | 1, m + 1, r, x, y));
}
} st;
int main()
{
setup();
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
st.Build(1, 1, n);
cin >> q;
for (int i = 0; i < q; ++i)
{
cin >> b >> c;
query[b].push_back({c, i});
}
for (int i = n; i >= 1; --i)
{
while (!v.empty())
{
st.Update(1, 1, n, v.back() * 2 - i, n, a[i] + a[v.back()]);
if (a[v.back()] <= a[i])
{
v.pop_back();
}
else
{
break;
}
}
v.push_back(i);
for (auto & j : query[i])
{
res[j.second] = st.Get(1, 1, n, i, j.first);
}
}
for (int i = 0; i < q; ++i)
{
cout << res[i] << "\n";
}
return 0;
}
