#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;
int n, q;
const int N = 5e5 + 5;
const int L = (1 << 20);
int a[N];
vector<int> bigs[N];
vector<pair<int, int>> quer[N];
int seg[L][3];
void cre(int l, int r, int ind) {
if (l == r) {
seg[ind][0] = -inf;
seg[ind][1] = -inf;
seg[ind][2] = a[l];
return;
}
int m = (l + r) / 2;
cre(l, m, 2 * ind);
cre(m + 1, r, 2 * ind + 1);
seg[ind][0] = -inf;
seg[ind][1] = -inf;
seg[ind][2] = max(seg[2 * ind][2], seg[2 * ind + 1][2]);
}
void upd(int b, int x, int l, int r, int ind) {
if (b <= l) {
seg[ind][1] = max(seg[ind][1], x);
seg[ind][0] = max(seg[ind][0], seg[ind][1] + seg[ind][2]);
return;
}
if (r < b) {
return;
}
int m = (l + r) / 2;
upd(b, x, l, m, 2 * ind);
upd(b, x, m + 1, r, 2 * ind + 1);
seg[ind][0] = max(seg[ind][0], max(seg[2 * ind][0], seg[2 * ind + 1][0]));
}
pair<int, int> get(int b, int e, int l, int r, int ind) {
if (b <= l && r <= e) {
return mp(seg[ind][0], seg[ind][2]);
}
if (e < l || r < b) {
return mp(-inf, 0);
}
int m = (l + r) / 2;
pair<int, int> p1 = get(b, e, l, m, 2 * ind);
pair<int, int> p2 = get(b, e, m + 1, r, 2 * ind + 1);
return mp(max(seg[ind][1] + max(p1.se, p2.se), max(p1.fi, p2.fi)), max(p1.se, p2.se));
}
void init() {
}
void input() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> q;
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
quer[l].pb(mp(r, i));
}
}
void solve() {
vector<int> big;
for (int i = n; i >= 1; i--) {
while (!big.empty()) {
int x = big.back();
if (a[i] <= a[x]) {
break;
}
bigs[i].pb(x);
big.pop_back();
}
if (!big.empty()) {
bigs[i].pb(big.back());
}
big.pb(i);
}
cre(1, n, 1);
int ans[q + 1];
for (int l = n; l >= 1; l--) {
for (auto i : bigs[l]) {
upd(2 * i - l, a[l] + a[i], 1, n, 1);
}
for (auto p : quer[l]) {
ans[p.se] = get(l, p.fi, 1, n, 1).fi;
}
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << endl;
}
}
void output() {
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int number_of_testcases = 1;
//cin >> number_of_testcases;
while (number_of_testcases--) {
init();
input();
solve();
output();
}
return 0;
}
