#include<bits/stdc++.h>
using namespace std;
const int N = (int)5e5+7;
const int M = (int)2e5+7;
const int inf = (int)1e9+7;
int n, q, a[N], b[N], ans[N];
pair<int, int> suf[N];
int L[N], R[N];
vector<pair<int, int> > Q[N];
vector<int> adj[N];
int add[4*N], t[4*N], mx[4*N];
void build(int v, int tl, int tr) {
if(tl == tr) {
t[v] = a[tl];
return;
}
int mid = (tl+tr)/2;
build(v*2, tl, mid);
build(v*2+1, mid+1, tr);
t[v] = max(t[v*2], t[v*2+1]);
mx[v] = t[v];
}
void push(int v, int tl, int tr) {
if(tl != tr) {
add[v*2] = max(add[v*2], add[v]);
add[v*2+1] = max(add[v*2+1], add[v]);
}
mx[v] = max(mx[v], t[v]+add[v]);
}
void upd(int v, int tl, int tr, int l, int r, int x) {
push(v, tl, tr);
if(tl>r || l>tr) {
return;
}
if(tl >= l && tr<= r) {
add[v] = max(add[v], x);
push(v, tl, tr);
return;
}
int mid = (tl+tr)>>1;
upd(v*2, tl, mid, l, r, x);
upd(v*2+1, mid+1, tr, l, r, x);
mx[v] = max(mx[v*2], mx[v*2+1]);
}
void upd(int l, int r, int x) {
if(l>r) {
return;
}
upd(1, 1, n, l, r, x);
}
int get(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if(tl >= l && tr <= r) {
return mx[v];
}
if(tl>r || l > tr) {
return 0;
}
int mid = (tl+tr)/2;
return max(get(v*2, tl, mid, l, r), get(v*2+1, mid+1, tr, l, r));
}
int get(int l, int r) {
if(l>r) {
return 0;
}
return get(1, 1, n, l, r);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
build(1, 1, n);
cin >> q;
stack<int> st;
for(int i = 1; i <= n; ++i) {
L[i] = i;
while(!st.empty() && a[st.top()]<a[i]) {
L[i]=L[st.top()];
st.pop();
}
st.push(i);
}
while(!st.empty()) {
continue;
}
for(int i = n; i >= 1; --i) {
R[i] = i;
while(!st.empty() && a[st.top()]<a[i]) {
R[i] = R[st.top()];
st.pop();
}
st.push(i);
}
for(int i = 1; i <= n; ++i) {
if(R[i]+1<=n) {
adj[i].push_back(R[i]+1);
}
if(L[i]-1>=1) {
adj[L[i]-1].push_back(i);
}
}
for(int i = 1; i <= q; ++i) {
int l, r;
cin >> l >> r;
Q[l].push_back({r, i});
}
for(int l = n; l >= 1; --l) {
{
for(int j : adj[l]) {
int i = l;
upd(2*j-i, n, a[i]+a[j]);
}
}
for(auto [r, i] : Q[l]) {
ans[i] = max(ans[i], get(l, r));
}
}
for(int i = 1; i <= q; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
