#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = -1e18;
int N, Q;
vector<long long> A;
vector<pair<int, int>> queries;
vector<long long> answers;
// Sparse table for RMQ
vector<vector<long long>> rmq_table;
vector<int> log_table;
void build_rmq() {
log_table.resize(N + 1);
log_table[1] = 0;
for (int i = 2; i <= N; ++i) {
log_table[i] = log_table[i / 2] + 1;
}
int max_log = log_table[N];
rmq_table.resize(max_log + 1, vector<long long>(N + 1, 0));
for (int i = 1; i <= N; ++i) {
rmq_table[0][i] = A[i - 1];
}
for (int j = 1; j <= max_log; ++j) {
for (int i = 1; i + (1 << j) - 1 <= N; ++i) {
rmq_table[j][i] = max(rmq_table[j - 1][i], rmq_table[j - 1][i + (1 << (j - 1))]);
}
}
}
long long query_rmq(int l, int r) {
if (l > r) return -INF;
int len = r - l + 1;
int j = log_table[len];
return max(rmq_table[j][l], rmq_table[j][r - (1 << j) + 1]);
}
// Fenwick tree (Binary Indexed Tree)
vector<long long> ft;
void update_ft(int idx, long long val) {
for (; idx <= N; idx += idx & -idx) {
ft[idx] = max(ft[idx], val);
}
}
long long query_ft(int idx) {
long long max_val = -INF;
for (; idx > 0; idx -= idx & -idx) {
max_val = max(max_val, ft[idx]);
}
return max_val;
}
struct Query {
int id;
int L, R;
long long ans;
};
// Custom comparison for sorting queries
bool compareQueries(const Query& a, const Query& b) {
return a.R < b.R;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
A.resize(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
// Convert to 1-based indexing for convenience
vector<long long> A1(N + 1);
for(int i = 0; i < N; ++i) {
A1[i+1] = A[i];
}
A = A1;
cin >> Q;
vector<Query> sorted_queries(Q);
for (int i = 0; i < Q; ++i) {
sorted_queries[i].id = i;
cin >> sorted_queries[i].L >> sorted_queries[i].R;
}
sort(sorted_queries.begin(), sorted_queries.end(), compareQueries);
build_rmq();
ft.assign(N + 1, -INF);
vector<long long> max_prefix_A(N + 1, -INF);
for(int i = 1; i <= N; ++i) {
max_prefix_A[i] = max(max_prefix_A[i-1], A[i]);
}
// dp[b] stores max(A_a + A_b) for a fixed b, a<b
vector<long long> dp_sum_ab(N + 1, -INF);
for(int b = 2; b <= N; ++b) {
dp_sum_ab[b] = max_prefix_A[b-1] + A[b];
}
answers.resize(Q);
int query_idx = 0;
for (int c = 1; c <= N; ++c) {
for(int b=1; b<c; ++b){
int a_min = 2*b - c;
if(a_min < 1) a_min = 1;
if(a_min < b){
long long val = A[c] + A[b] + query_rmq(a_min, b-1);
update_ft(b, val);
}
}
while (query_idx < Q && sorted_queries[query_idx].R == c) {
int L = sorted_queries[query_idx].L;
long long max_val = query_ft(c);
long long temp_max = -INF;
for(int b = L+1; b < c; ++b){
int a_min = 2*b-c;
if(a_min < L) a_min = L;
if(a_min < b){
temp_max = max(temp_max, A[c] + A[b] + query_rmq(a_min, b-1));
}
}
sorted_queries[query_idx].ans = temp_max;
query_idx++;
}
}
// Sort back to original order
vector<long long> final_answers(Q);
for(int i = 0; i < Q; ++i) {
final_answers[sorted_queries[i].id] = sorted_queries[i].ans;
}
for(int i = 0; i < Q; ++i) {
cout << final_answers[i] << "\n";
}
return 0;
}
