#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 5e5 + 6;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
struct node{
ll lz , s , res;
}s[maxn * 4];
int n , a[maxn];
void push(int x , bool key){
s[x].res = max(s[x].res,s[x].s+s[x].lz);
if(key){
s[x * 2].lz= max(s[x * 2].lz , s[x].lz);
s[x * 2 + 1].lz= max(s[x * 2 +1 ].lz , s[x].lz);
}
}
void build(int x , int l , int r){
s[x].lz = -2e9;
if(l == r){
s[x].s = a[l];
return;
}
int mid = l + r >> 1;
build(x*2,l,mid);build(x*2+1,mid+1,r);
s[x].s = max(s[x*2].s,s[x*2+1].s);
}
void update(int x , int l , int r , int L , int R , ll val){
push(x,l!=r);
if(L > r || l > R)return;
if(L <= l && r <= R){
s[x].lz = max(s[x].lz,val);
push(x,l!=r);
return;
}
int mid = l + r >> 1;
update(x*2,l,mid,L,R,val);
update(x*2+1,mid+1,r,L,R,val);
s[x].res = max(s[x*2].res,s[x*2+1].res);
}
ll query(int x , int l , int r , int L , int R){
push(x,l!=r);
if(L > r || l > R)return 0;
if(L <= l && r <= R)return s[x].res;
int mid = l + r >> 1;
return max(query(x*2,l,mid,L,R),query(x*2+1,mid+1,r,L,R));
}
int q;
ll ans[maxn];
vector<ii> Q[maxn];
vector<int> U[maxn];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP","r",stdin);
freopen(taskname".OUT","w",stdout);
}
cin >> n;
for(int i = 1 ; i <= n ; ++i)cin >> a[i];
build(1,1,n);
vector<int> s;
for(int i = 1 ; i <= n ; ++i){
while(s.size() && a[s.back()] <= a[i]){
U[s.back()].pb(i);s.pop_back();
}
if(s.size())U[s.back()].pb(i);
s.pb(i);
}
cin >> q;
for(int i = 1 ; i <= q ; ++i){
int u , v;cin >> u >> v;Q[u].pb(mp(v,i));
}
for(int i = n ; i >= 1 ; --i){
for(auto & b : U[i]){
if(b * 2 - i <= n){
update(1,1,n,b*2-i,n,a[b]+a[i]);
// cout << i << " " << b << " " << b * 2 - i << endl;
}
}
for(auto & c : Q[i]){
ans[c.second] = query(1,1,n,i,c.first);
}
}
for(int i = 1 ; i <= q ; ++i)cout << ans[i] << '\n';
}
