#include <bits/stdc++.h>
using namespace std;
const int MAX = 5e5 + 5;
int n, a[MAX], q, ans[MAX];
vector <pair <int, int>> queries[MAX];
int Max_cur[MAX << 2], Max_add[MAX << 2], Max_val[MAX << 2];
void build(int s, int l, int r){
if (l == r){
Max_cur[s] = a[l];
Max_val[s] = a[l];
return;
}
int mid = l + r >> 1;
build(s << 1, l, mid);
build(s << 1 | 1, mid + 1, r);
Max_cur[s] = max(Max_cur[s << 1], Max_cur[s << 1 | 1]);
Max_val[s] = Max_cur[s];
}
void update(int u, int v, int val, int s = 1, int l = 1, int r = n){
if (u <= l && r <= v){
Max_add[s] = max(Max_add[s], val);
Max_val[s] = max(Max_val[s], Max_cur[s] + val);
return;
}
int mid = l + r >> 1;
if (mid >= u) update(u, v, val, s << 1, l, mid);
if (mid < v) update(u, v, val, s << 1 | 1, mid + 1, r);
Max_val[s] = max({Max_val[s << 1], Max_val[s << 1 | 1], Max_cur[s] + Max_add[s]});
}
pair <int, int> get(int u, int v, int s = 1, int l = 1, int r = n){
if (v < l || u > r) return make_pair(0, 0);
if (u <= l && r <= v) return make_pair(Max_val[s], Max_cur[s]);
int mid = l + r >> 1;
auto [a, b] = get(u, v, s << 1, l, mid);
auto [c, d] = get(u, v, s << 1 | 1, mid + 1, r);
return make_pair(max({a, c, max(b, d) + Max_add[s]}), max(b, d));
}
void process(){
cin >> n;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
build(1, 1, n);
cin >> q;
for (int i = 1; i <= q; ++ i){
int l, r; cin >> l >> r;
queries[l].emplace_back(r, i);
}
auto add = [&](int i, int j) -> void {
int k = j + (j - i);
if (k > n) return;
update(k, n, a[i] + a[j]);
};
vector <int> stk = {n};
for (int l = n - 1; l >= 1; -- l){
while (stk.size() && a[l] >= a[stk.back()]){
add(l, stk.back());
stk.pop_back();
}
if (stk.size()) add(l, stk.back());
stk.push_back(l);
for (auto [r, id] : queries[l]) ans[id] = get(l, r).first;
}
for (int i = 1; i <= q; ++ i)
cout << ans[i] << "\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
process();
return 0;
}
