#include <bits/stdc++.h>
#define N 500010
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, q, v[N], C[5010][5010], menor[5010][5010], dp[5010][5010];
int ans, tree[4*N];
void build(int nod, int a, int b)
{
if(a == b)
{
tree[nod] = v[a];
return;
}
build(2*nod, a, (a+b)/2);
build(2*nod + 1, (a + b)/2 + 1, b);
tree[nod] = max(tree[2*nod], tree[2*nod + 1]);
}
int query(int nod, int a, int b, int i, int j)
{
if(j < a or i > b) return 0;
if(i <= a and j >= b) return tree[nod];
return max(query(2*nod, a, (a+b)/2, i, j), query(2*nod + 1, (a+b)/2 + 1, b, i, j));
}
int solve(int i, int j)
{
if(i > j) return 0;
if(dp[i][j] != -1) return dp[i][j];
return dp[i][j] = max({solve(i + 1, j), solve(i, j - 1), C[i][j]});
}
int32_t main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i = 1; i <= n; i++) cin>>v[i];
if(n <= 5000)
{
memset(dp, -1, sizeof dp);
for(int i = 1; i <= n; i++)
{
menor[i][i] = v[i];
for(int j = i + 1; j <= n; j++)
menor[i][j] = max(menor[i][j - 1], v[j]);
}
for(int i = 1; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
int mid = (i + j)/2;
C[i][j] = menor[i + 1][mid] + v[i] + v[j];
}
}
cin>>q;
for(int i = 1, l, r; i <= q; i++)
{
cin>>l>>r;
cout<<solve(l, r)<<"\n";
}
}
else
{
build(1, 1, n);
vector<pii> val;
for(int i = 1; i <= n; i++) val.push_back({v[i], i});
sort(val.rbegin(), val.rend());
for(int i = 0; i < min(70, (int)val.size()); i++)
{
int vi = val[i].f, p = val[i].s;
for(int x = 1; x <= n; x++)
{
int mid = (x + p)/2;
int l = min(x, p), r = max(x, p);
int opt = query(1, 1, n, l + 1, mid);
ans = max(ans, opt + v[l] + v[r]);
}
}
int a, b;
cin>>a>>b;
cout<<ans<<"\n";
}
}
