#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define base 29
#define eps 1e-8
int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=4e5+1;
const int mod=1e9+7;
int n,a[maxn],mx[4*maxn],tree[4*maxn],lazy[4*maxn],ans[maxn],q;
vector<ii>query[maxn];
void build(int id,int l,int r)
{
if(l==r)
{
tree[id]=mx[id]=a[l];
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
tree[id]=max(tree[id*2],tree[id*2+1]);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
void down(int id)
{
int &w=lazy[id];
tree[id*2]=max(tree[id*2],mx[id*2]+w);
tree[id*2+1]=max(tree[id*2+1],mx[id*2+1]+w);
lazy[id*2]=max(lazy[id*2],w);
lazy[id*2+1]=max(lazy[id*2+1],w);
w=0;
}
void update(int id,int l,int r,int u,int v,int w)
{
if(u>r||v<l)return;
if(u<=l&&v>=r)
{
tree[id]=max(tree[id],mx[id]+w);
lazy[id]=max(lazy[id],w);
return;
}
int mid=(l+r)/2;
down(id);
update(id*2,l,mid,u,v,w);
update(id*2+1,mid+1,r,u,v,w);
tree[id]=max(tree[id*2],tree[id*2+1]);
}
int get(int id,int l,int r,int u,int v)
{
if(u>r||v<l)return 0;
if(u<=l&&v>=r)return tree[id];
down(id);
int mid=(l+r)/2;
return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
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;
query[l].push_back({r,i});
}
build(1,1,n);
stack<int>s;
for(int i=n;i>=1;i--)
{
while(!s.empty()&&a[i]<=a[s.top()])
{
update(1,1,n,2*s.top()-i,n,a[i]+a[s.top()]);
s.pop();
}
if(s.size())update(1,1,n,2*s.top()-i,n,a[i]+a[s.top()]);
for(ii x:query[i])
{
ans[x.se]=get(1,1,n,i,x.fi);
}
s.push(i);
}
for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}
