#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
const ll inf = 1e17;
class node
{
public:
ll mx, mx_arr, ret;
node(ll mx = 0, ll mx_arr = 0, ll ret = 0):
mx(mx), mx_arr(mx_arr), ret(ret) {}
node operator + (const node & other) const
{
node res;
res.ret = max({ret, other.ret, mx_arr + other.mx});
res.mx = max(mx, other.mx);
res.mx_arr = max(mx_arr, other.mx_arr);
return res;
}
};
class segment_tree
{
vector<node> ST;
public:
segment_tree(int n)
{
ST.assign(4 * n + 5, node(-inf, -inf, -inf));
}
#define lc id << 1
#define rc id << 1 | 1
void update(int id, int l, int r, int pos, ll val, bool need)
{
if (l > pos || r < pos) return;
if (l == r){
if (need) ST[id].mx = max(ST[id].mx, val);
else ST[id].mx_arr = max(ST[id].mx_arr, val);
ST[id].ret = max(-inf, ST[id].mx + ST[id].mx_arr);
return;
}
int mid = (l + r) / 2;
update(lc, l, mid, pos, val, need); update(rc, mid + 1, r, pos, val, need);
ST[id] = ST[lc] + ST[rc];
}
node sum(int id, int l, int r, int L, int R)
{
if (L > R || l > R || L > r) return node(-inf, -inf, -inf);
if (L <= l && r <= R) return ST[id];
int mid = (l + r) / 2;
return sum(lc, l, mid, L, R) + sum(rc, mid + 1, r, L, R);
}
#undef lc
#undef rc
};
int N, Q;
int a[maxn];
vector<pair<int, int>> query[maxn];
ll res[maxn];
signed main(void)
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen("A.INP", "r")){
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
}
cin >> N;
vector<int> st;
vector<pair<int, int>> good;
for (int i = 1; i <= N; ++i){
cin >> a[i];
while (st.size() && a[i] >= a[st.back()]){
good.pb(mp(st.back(), i));
st.pop_back();
}
if (st.size())
good.pb(mp(st.back(), i));
st.pb(i);
}
sort(good.rbegin(), good.rend());
///for (auto & all : good) cerr << all.fi << ' ' << all.se << '\n';
cin >> Q;
for (int i = 1; i <= Q; ++i){
int l, r; cin >> l >> r;
query[l].pb(mp(r, i));
}
segment_tree tree(N);
int j = 0;
for (int i = N; i >= 1; --i){
tree.update(1, 1, N, i, a[i], true);
while (j < (int)good.size() && good[j].fi >= i){
int pos = 2 * good[j].se - good[j].fi;
ll val = a[good[j].fi] + a[good[j].se];
if (pos <= N) tree.update(1, 1, N, pos, val, false);
++j;
}
for (auto & all : query[i]){
res[all.se] = tree.sum(1, 1, N, i, all.fi).ret;
}
}
for (int i = 1; i <= Q; ++i){
cout << res[i] << '\n';
}
}
