#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int z[1000005];
vector<int> v[1000005];
struct node{
int val,ab,c;
};
node f[4000005];
vector<pair<int,int>> q[1000005];
int res[1000005];
void push(int id,int val){
if (f[id].ab<val){
f[id].val=max(val+f[id].c,f[id].val);
f[id].ab=val;
}
}
void build(int id,int l,int r){
if (l==r){
f[id].c=z[l];
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
f[id].c=max(f[id*2].c,f[id*2+1].c);
}
void update(int id,int l,int r,int x,int y,int val){
if (x>r || y<l){
return;
}
if (l>=x && y>=r){
push(id,val);
return;
}
push(id*2,f[id].ab);
push(id*2+1,f[id].ab);
int mid=(l+r)/2;
update(id*2,l,mid,x,y,val);
update(id*2+1,mid+1,r,x,y,val);
f[id].val=max(f[id*2].val,f[id*2+1].val);
}
int get(int id,int l,int r,int x,int y){
if (x>r || y<l){
return 0;
}
if (l>=x && y>=r){
return f[id].val;
}
push(id*2,f[id].ab);
push(id*2+1,f[id].ab);
int mid=(l+r)/2;
return max(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y));
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a;
for (int i=1;i<=a;i++){
cin >> z[i];
}
stack<int> st;
for (int i=1;i<=a;i++){
while (st.size() && z[st.top()]<=z[i]){
v[st.top()].push_back(i);
st.pop();
}
if (st.size()){
v[st.top()].push_back(i);
}
st.push(i);
}
build(1,1,a);
int t;
cin >> t;
for (int i=1;i<=t;i++){
int l,r;
cin >> l >> r;
q[l].push_back({r,i});
}
for (int i=a;i>=1;i--){
for (auto p:v[i]){
int range=2*p-i;
int val=z[i]+z[p];
update(1,1,a,range,a,val);
}
for (auto p:q[i]){
res[p.second]=get(1,1,a,i,p.first);
}
}
for (int i=1;i<=t;i++){
cout << res[i] << "\n";
}
return 0;
}
