#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=6e5+13;
int n, q;
ll a[N];
struct Segtree{
ll st[N << 2];
ll vmax[N << 2];
ll lazy[N << 2];
void fix(int id, int l, int r){
if(!lazy[id]) return;
st[id]=max(st[id], lazy[id]+vmax[id]);
lazy[id << 1]=max(lazy[id << 1], lazy[id]);
lazy[id << 1 | 1]=max(lazy[id << 1 | 1], lazy[id]);
lazy[id]=0;
}
void build(int id, int l, int r){
if(l==r){
vmax[id]=a[l];
return;
}
int mid=l+r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid+1, r);
vmax[id]=max(vmax[id << 1], vmax[id << 1 | 1]);
}
void update(int id, int l, int r, int u, int v, ll val){
fix(id, l, r);
if(l > v || r < u) return;
if(u<=l && r<=v){
lazy[id]=max(lazy[id], val);
fix(id, l, r);
return;
}
int mid=l+r >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid+1, r, u, v, val);
st[id]=max(st[id << 1], st[id << 1 | 1]);
}
ll get(int id, int l, int r, int u, int v){
fix(id, l, r);
if(l > v || r < u) return -1e9;
if(u<=l && r<=v) return st[id];
int mid=l+r >> 1;
int get1=get(id << 1, l, mid, u, v);
int get2=get(id << 1 | 1, mid+1, r, u, v);
return max(get1, get2);
}
void update(int u, int v){
update(1, 1, n, u, n, v);
}
int get(int u, int v){
return get(1, 1, n, u, v);
}
} st;
stack<int> s;
vector<int> nxt[N];
vector<int> qr[N];
ll l[N], r[N];
ll res[N];
void scan(){
cin >> n;
for(int i=1; i<=n; i++){
cin >> a[i];
}
st.build(1, 1, n);
for(int i=n; i>=1; i--){
while(!s.empty() && a[s.top()] <= a[i]){
nxt[i].push_back(s.top());
s.pop();
}
if(s.size()) nxt[i].push_back(s.top());
s.push(i);
}
cin >> q;
for(int i=1; i<=q; i++){
cin >> l[i] >> r[i];
qr[l[i]].push_back(i);
}
}
void solve(){
for(int i=n; i>=1; i--){
for(int j: nxt[i]){
if(2*j-i<=n){
//cout << "? " << i << ' ' << j << ' ' << 2*j-i << ' ' << a[i]+a[j] << '\n';
st.update(2*j-i, a[i]+a[j]);
}
}
for(int id: qr[i]){
res[id]=st.get(i, r[id]);
}
}
for(int i=1; i<=q; i++){
cout << res[i] << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
scan();
solve();
}
