//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;
typedef pair<ll,ll> pii;
typedef tuple<int,int,int> tp;
const int N = 1e6 + 5;
//const int mod = 1e9 + 7;
const ll oo = 5e18;
int n, a[N], T[N << 2], lz[N << 2], q, kq[N], val[N << 2];
void build(int i,int l,int r){
if(l == r){
val[i] = T[i] = a[l];
return;
}
int mid = (l + r) / 2;
build(i << 1, l, mid);
build(i << 1|1, mid + 1, r);
val[i] = T[i] = max(T[i << 1], T[i << 1|1]);
}
void update(int i,int l,int r,int u,int v, int x){
if(l > r || l > v || r < u) return;
if(u <= l && r <= v){
val[i] = max(val[i], T[i] + x);
lz[i] = max(lz[i], x);
return;
}
if(lz[i]){
val[i << 1] = max(val[i << 1], T[i << 1] + lz[i]);
val[i << 1|1] = max(val[i << 1|1], T[i << 1|1] + lz[i]);
lz[i << 1] = max(lz[i << 1], lz[i]);
lz[i << 1|1] = max(lz[i << 1|1], lz[i]);
lz[i] = 0;
}
int mid = (l + r) / 2;
update(i << 1, l, mid, u, v, x);
update(i << 1|1, mid + 1, r, u, v, x);
val[i] = max(val[i << 1], val[i << 1|1]);
}
int get(int i,int l,int r,int u,int v){
if(l > r || l > v || r < u) return 0;
if(u <= l && r <= v) return val[i];
if(lz[i]){
val[i << 1] = max(val[i << 1], T[i << 1] + lz[i]);
val[i << 1|1] = max(val[i << 1|1], T[i << 1|1] + lz[i]);
lz[i << 1] = max(lz[i << 1], lz[i]);
lz[i << 1|1] = max(lz[i << 1|1], lz[i]);
lz[i] = 0;
}
int mid = (l + r) / 2;
return max(get(i << 1, l, mid, u, v), get(i << 1|1, mid + 1, r, u, v));
}
#define lpv
#ifdef lpv
vector<pii> vr[N];
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
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;
vr[l].pb({r, i});
}
stack<int> st;
build(1, 1, n);
st.push(n);
for(int i = n - 1; i >= 1; i --){
if(i + 2 <= n) update(1, 1, n, i + 2, n, a[i] + a[i + 1]);
while(!st.empty() && a[i] >= a[st.top()]){
int tmp = st.top() - i;
if(st.top() + tmp <= n) update(1, 1, n, st.top() + tmp, n, a[i] + a[st.top()]);
st.pop();
}
if(!st.empty()){
int tmp = st.top() - i;
if(st.top() + tmp <= n) update(1, 1, n, st.top() + tmp, n, a[i] + a[st.top()]);
}
st.push(i);
for(auto [j, id] : vr[i]) kq[id] = get(1, 1, n, i + 2, j);
}
for(int i = 1; i <= q; i ++) cout << kq[i] << "\n";
}
#endif // lpv
