#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+2;
const int inf=3e9+7;
int ar[N],ans[N];
struct node{
int lef=-inf,rig=-inf,ans=-inf;
} it[4*N];
vector<pair<int,int> > lis,query[N];
vector<int> upd_lis[N];
void get(int idx,int l,int r){
it[idx].lef=max(it[2*idx].lef,it[2*idx+1].lef);
it[idx].rig=max(it[2*idx].rig,it[2*idx+1].rig);
it[idx].ans=max(it[2*idx].ans,max(it[2*idx+1].ans,it[2*idx].lef+it[2*idx+1].rig));
}
node merge(node a,node b){
node ans;
ans.lef=max(a.lef,b.lef);
ans.rig=max(a.rig,b.rig);
ans.ans=max(a.ans,max(b.ans,a.lef+b.rig));
return ans;
}
void init(int idx,int l,int r){
if(l==r){
it[idx].rig=ar[l];
return;
}
init(2*idx,l,(l+r)/2);
init(2*idx+1,(l+r)/2+1,r);
get(idx,l,r);
}
void upd(int idx,int l,int r,int pos,int val){
if(l>pos||r<pos){
return;
}
if(l==r){
it[idx].lef=max(it[idx].lef,val);
it[idx].ans=max(it[idx].ans,it[idx].lef+it[idx].rig);
return;
}
upd(2*idx,l,(l+r)/2,pos,val);
upd(2*idx+1,(l+r)/2+1,r,pos,val);
get(idx,l,r);
}
node getmax(int idx,int l,int r,int lef,int rig){
if(l>rig||r<lef){
return node();
}
if(l>=lef&&r<=rig){
return it[idx];
}
return merge(getmax(2*idx,l,(l+r)/2,lef,rig),getmax(2*idx+1,(l+r)/2+1,r,lef,rig));
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,i,j,k,l,q;
cin>>n;
for(i=1;i<=n;i++){
cin>>ar[i];
while(lis.size()){
upd_lis[lis.back().second].push_back(i);
if(lis.back().first>ar[i]){
break;
}
else{
lis.pop_back();
}
}
lis.push_back({ar[i],i});
}
init(1,1,n);
cin>>q;
for(i=1;i<=q;i++){
cin>>j>>k;
query[j].push_back({k,i});
}
for(i=n;i>0;i--){
for(j=0;j<upd_lis[i].size();j++){
if(2*upd_lis[i][j]-i>n){
continue;
}
upd(1,1,n,2*upd_lis[i][j]-i,ar[i]+ar[upd_lis[i][j]]);
}
for(j=0;j<query[i].size();j++){
node wow=getmax(1,1,n,i,query[i][j].first);
ans[query[i][j].second]=wow.ans;
}
}
for(i=1;i<=q;i++){
cout<<ans[i]<<'\n';
}
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
*/
Compilation message
Compilation timeout while compiling jumps
