#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, q, a, b, c, sp[20][500000];
long long res, pre[5000][5000];
inline int Get(int l, int r)
{
int k = __lg(r - l + 1);
return max(sp[k][l], sp[k][r - (1 << k) + 1]);
}
int main()
{
setup();
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> sp[0][i];
}
for (int i = 1; i <= __lg(n); ++i)
{
for (int j = 0; j + (1 << i) <= n; ++j)
{
sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
}
}
if (n <= 5000)
{
for (int x = 2; x < n; ++x)
{
for (int i = 0, j = x; j < n; ++i, ++j)
{
pre[i][j] = sp[0][i] + sp[0][j] + Get(i + 1, (i + j) / 2);
pre[i][j] = max({pre[i][j], pre[i + 1][j], pre[i][j - 1]});
}
}
}
cin >> q;
while (q--)
{
cin >> a >> b;
a--;
b--;
if (n <= 5000)
{
cout << pre[a][b] << "\n";
}
}
return 0;
}
