感觉这题做太晚了，已经有神仙告诉过我这题是倍增了，于是难度直接降到黄。不过既然是经典好题还是写篇题解总结一下吧。
题面有点长，要耐心。
都知道是倍增了，直接写做法吧，思路只需“倍增”二字
考虑预处理出：
-
(A[i][j]) 表示这次由 (A) 开车，从城市 (i) 开始 (AB) 轮流交换开 (2^j) 次后到达的节点编号。
-
(d[i][j]) 表示这次由 (A) 开车，从城市 (i) 开始 (AB) 轮流交换开 (2^j) 次 (A) 开的路径长度。
-
(S[i][j]) 表示这次由 (A) 开车，从城市 (i) 开始 (AB) 轮流交换开 (2^j) 次总共开的路径长度。
预处理这些我们需要知道从每一个点开始往后：离它最近的城市以及次近的城市。
这个可以从后往前扫，搞个 set 存一下已经加入的城市高度，然后查询一下 (h_i) 的前驱后继，前驱的前驱，后继的后继，搞几个 if 判断一下最近和次近。
对于第一个询问，可以发现和第二个询问及其类似，只需要设起点从 (1) 到 (n) 跑一遍二询问，几个 if 判断一下哪个更优。
关于二询问，倍增从 (log n) 往 (0) 跑，记录当前 (A) 已经经过的路径长度以及总路径长度，如果总路径长度加上再走一步的路径长度不大于 (x) 那么就走，走到底即可。
那么 (B) 走的路径长度就是总路径长度减去 (A) 走的路径长度。
代码也有点细节，毕竟不是点倍增而是边倍增，要想清楚。那几个 if 不要写错。
倍增的时候要注意一下，因为是 (AB) 轮流走，所以 (2^1) 的步长要手动写出来
总复杂度 (O(nlog n))
#include<bits/stdc++.h>
using namespace std;
#define mkp(x,y) make_pair(x,y)
#define fi first
#define se second
typedef long long LL;
typedef double db;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f?x:-x;
}
#define N 100005
#define LOG 18
#define inf 20000000000000ll//2e13
int n,h[N],m;
int A[N][LOG],lg[N],B[N];
LL d[N][LOG],S[N][LOG],dB[N];
void init(){
multiset<pair<LL,int> >s;
s.insert(mkp(inf,0)),s.insert(mkp(inf,0)),s.insert(mkp(-inf,0)),s.insert(mkp(-inf,0));
for(int i=n;i>=1;--i){
set<pair<LL,int> >::iterator it;
it=s.lower_bound(mkp(h[i],114514)),++it;
pair<LL,int> x=*it--,y=*it--,z=*it--,k=*it;
if(h[i]-z.fi<=y.fi-h[i]){
B[i]=z.se,dB[i]=h[i]-z.fi;
if(h[i]-k.fi<=y.fi-h[i])A[i][0]=k.se,d[i][0]=h[i]-k.fi;
else A[i][0]=y.se,d[i][0]=y.fi-h[i];
}else {
B[i]=y.se,dB[i]=y.fi-h[i];
if(h[i]-z.fi<=x.fi-h[i])A[i][0]=z.se,d[i][0]=h[i]-z.fi;
else A[i][0]=x.se,d[i][0]=x.fi-h[i];
}
s.insert(mkp(h[i],i));
}
lg[0]=-1;for(int i=1;i<=n;++i)lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;++i)
A[i][1]=B[A[i][0]],d[i][1]=d[i][0],
S[i][0]=d[i][0],S[i][1]=S[i][0]+dB[A[i][0]];
for(int j=2;j<=lg[n];++j)
for(int i=1;i<=n;++i)
A[i][j]=A[A[i][j-1]][j-1],d[i][j]=d[i][j-1]+d[A[i][j-1]][j-1],
S[i][j]=S[i][j-1]+S[A[i][j-1]][j-1];
h[0]=-1e9-114514;
}
pair<LL,LL>solve2(int s,int x){
int u=s;LL sumA=0,sum=0;
for(int i=lg[n];i>=0;--i)if(A[u][i]&&S[u][i]+sum<=x)sumA+=d[u][i],sum+=S[u][i],u=A[u][i];
return mkp(sumA,sum-sumA);
}
const db eps=1e-10;
void solve1(){
int x=read();
pair<LL,LL>now=mkp(114514,0);
int res=0;
for(int i=1;i<=n;++i){
pair<LL,LL>tmp=solve2(i,x);
if(!tmp.se&&!now.se){
if(h[i]>h[res])res=i,now=tmp;
}else if(tmp.se){
if(1.*now.fi/now.se>1.*tmp.fi/tmp.se)res=i,now=tmp;
}
}
printf("%d
",res);
}
signed main(){
n=read();
for(int i=1;i<=n;++i)h[i]=read();
init();
solve1();
for(m=read();m;--m){
int s=read(),x=read();
pair<LL,LL>tmp=solve2(s,x);
printf("%lld %lld
",tmp.fi,tmp.se);
}
return 0;
}