#include "bits/stdc++.h"
using namespace std;
#define ffor(n) for(int i = 0; i < n; i++)
#define fffor(n) for(int j = 0; j < n; j++)
#define uwu ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize("Ofast")
const int INF = 1e9 + 7;
const long long INF2 = 1e17;
struct node{
int value;
node() {
value = 0;
}
node(int _value) {
value = _value;
}
};
struct segmenttree{
int n, n2 = 1;
vector <node> tree;
// CHANGE THIS
node merge(node p, node q) {
return max(p.value, q.value);
}
segmenttree(vector <node>& v) {
n = v.size();
while(n2 < n) n2 *= 2;
tree = vector <node>(2 * n2);
for(int i = 0; i < n; i++) {
tree[i + n2] = v[i];
}
for(int i = n2 - 1; i >= 1; i--) {
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
}
void update(int pos, node value) {
pos += n2 - 1;
tree[pos] = value; // AND POSSIBLY THIS
while(pos > 1) {
pos /= 2;
tree[pos] = merge(tree[2 * pos], tree[2 * pos + 1]);
}
}
node query(int current, int a, int b, int l, int r, int node_span) {
if (a <= l && r <= b) {
return tree[current];
}
else if (a > r || l > b) {
return node();
}
else {
int child_span = node_span / 2;
return merge(query(2 * current, a, b, l, l + child_span - 1, child_span),
query(2 * current + 1, a, b, l + child_span, r, child_span));
}
}
node query(int a, int b) {
return query(1, a, b, 1, n2, n2);
}
};
int main(void) {
uwu
int n; cin >> n;
vector <long long> v(n);
ffor(n) cin >> v[i];
/*
* let dp[i][j] -> max answer if we start at i and end at j
* we query the maximum in range (i + 1, (i + j) / 2)
*/
vector <node> temp(n);
ffor(n) temp[i] = v[i];
segmenttree tree(temp);
vector <vector <long long>> dp(n, vector <long long>(n));
for(int i = 0; i < n; i++) {
for(int j = i + 2; j < n; j++) {
int left = i + 1, right = (i + j) / 2;
int maximum = tree.query(left + 1, right + 1).value;
dp[i][j] = v[i] + v[j] + maximum;
}
}
vector <vector <long long>> dp2(n, vector <long long>(n, -1));
auto update = [&] (int left, int right, auto&& update) -> void {
if (dp2[left][right] != -1) return;
if (left == right) {
dp2[left][right] = 0;
}
else {
update(left + 1, right, update);
update(left, right - 1, update);
dp2[left][right] = max({dp[left][right], dp2[left][right - 1], dp2[left + 1][right]});
}
};
update(0, n - 1, update);
int q; cin >> q;
ffor(q) {
int a, b; cin >> a >> b;
a--; b--;
cout << dp2[a][b] << '\n';
}
}
/*
C:\Users\kenne\OneDrive\Desktop\competitive_programming\main.cpp
*/
