#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=5e5+1;
int n,q;
int a[nmax],ans[nmax];
vector<pii> query[nmax];
vector<int> nxt[nmax];
void input()
{
cin >> n;
FOR(i,1,n) cin >> a[i];
cin >> q;
FOR(i,1,q)
{
int l,r; cin >> l >> r;
query[l].push_back({r,i});
}
}
struct SEGTREE
{
vector<pii> tree;
vector<int> lazy;
int n=0;
void build(int id,int l,int r)
{
if(l==r)
{
tree[id]={a[l],a[l]};
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
tree[id].fi=max(tree[id*2].fi,tree[id*2+1].fi);
tree[id].se=max(tree[id*2].se,tree[id*2+1].se);
}
SEGTREE(int N)
{
n=N;
tree.resize(4*n+5,{0,0});
lazy.resize(4*n+5,0);
build(1,1,n);
}
void down(int id,int l,int r)
{
tree[id].fi=max(tree[id].fi,tree[id].se+lazy[id]);
if(l!=r)
{
lazy[id*2]=max(lazy[id*2],lazy[id]);
lazy[id*2+1]=max(lazy[id*2+1],lazy[id]);
}
lazy[id]=0;
}
void update(int id,int l,int r,int a,int b,int val)
{
down(id,l,r);
if(b<l || r<a) return;
if(a<=l && r<=b)
{
lazy[id]+=val;
down(id,l,r);
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,a,b,val);
update(id*2+1,mid+1,r,a,b,val);
tree[id].fi=max(tree[id*2].fi,tree[id*2+1].fi);
}
int get(int id,int l,int r,int a,int b)
{
down(id,l,r);
if(b<l || r<a) return 0;
if(a<=l && r<=b) return tree[id].fi;
int mid=(l+r)/2;
return max(get(id*2,l,mid,a,b),get(id*2+1,mid+1,r,a,b));
}
void update(int l,int r,int val) { update(1,1,n,l,r,val); }
int get(int l,int r) { return get(1,1,n,l,r); }
};
void buildnxt()
{
stack<int> s;
REP(i,n,1)
{
if(s.empty()) s.push(i);
else
{
while(a[s.top()]<=a[i])
{
nxt[i].push_back(s.top());
s.pop();
if(s.empty()) break;
}
if(!s.empty()) nxt[i].push_back(s.top());
s.push(i);
}
}
}
void solve()
{
SEGTREE st(n);
buildnxt();
// FOR(i,1,n) {FORD(j,nxt[i]) cout << j << ' '; cout << '\n';}
REP(i,n,1)
{
FORD(j,nxt[i]) if(2*j-i<=n) st.update(2*j-i,n,a[i]+a[j]);
FORD(j,query[i]) ans[j.se]=st.get(i,j.fi);
}
FOR(i,1,q) cout << ans[i] << '\n';
}
signed main()
{
//freopen("kangaroo.in", "r", stdin);
//freopen("kangaroo.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
input();
solve();
}
