// Problem: P1081 [NOIP2012 提高组] 开车旅行
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1081
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define lowbit(x) ((x)&(-(x)))
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+10,M=10,G=32,INF=1e9+7;
inline int read(){
    int ret=0,f=1; 
	char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-f; ch=getchar(); }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void write(int x){        
    if(x<0){ putchar('-'); x=-x; }      
    if(x>9) write(x/10);     
    putchar(x%10+'0');     
}
int n,x0,m;
int h[N];
int s[N],x[N];
int pre[N],nxt[N];//list
int nxa[N],nxb[N];//下一个城市
int rk[N];//rk[i] 定义为 h[i] 在升序排列后的排名
int A[N][G],B[N][G],f[N][G];
int lg2[N];
struct Node{
	int id;
	int ht;
	bool operator<(const Node &B)const{
		return ht<B.ht||(ht==B.ht&&id<B.id);
	}
}cp[N],tmp_upt[M];
inline bool chk(int i){//是否合法
	return i>=1&&i<=n;
}
inline void upt(int pos,int rnk,int val){
	if(chk(rnk)) tmp_upt[pos]={rnk,val};
	else tmp_upt[pos]={-1,INF};
}
inline void del(int i){
	if(!chk(i)) return;
	nxt[pre[i]]=nxt[i];
	pre[nxt[i]]=pre[i];	
}
inline int dis(int i,int j){
	return (chk(i)&&chk(j))?abs(h[i]-h[j]):0;
}
inline bool equal(double a,double b){
	double c=a-b;
	if(c<0) c=-c;
	return c<0.000001;
}
inline pair<int,int> solve(int st,int lmt,int aed,int bed){
	//printf(" %d",st);
	for(int i=lg2[n]+1;i>=0;--i){
		if((f[st][i]&&aed+bed+A[st][i]+B[st][i]<=lmt)||i==0){
			if(i==0){
				if(aed+A[st][i]<=lmt) aed+=A[st][i];
				if(aed+bed+B[st][i]<=lmt) bed+=B[st][i];
				st=f[st][i];
				//printf("->%d(aed=%d,bed=%d)\n",st,aed,bed);
				break;
			}
			aed+=A[st][i];
			bed+=B[st][i];
			st=f[st][i];
			//printf("->%d(aed=%d,bed=%d)\n",st,aed,bed);
		}
	}
	//puts("");
	return make_pair(aed,bed);
}
inline void input(){
	n=read();
	for(int i=1;i<=n;++i){
		h[i]=read();
		cp[i]={i,h[i]};
	}
	x0=read();
	m=read();
	for(int i=1;i<=m;++i){
		s[i]=read();
		x[i]=read();
	}	
}
inline void init_list(){
	sort(cp+1,cp+n+1);
	for(int i=1;i<=n;++i){
		rk[cp[i].id]=i;
		pre[i]=i-1,nxt[i]=i+1;
	}
	// for(int i=1;i<=n;++i) printf("cp[%d]={%d,%d}\n",i,cp[i].id,cp[i].ht);
	// puts("");
	// for(int i=1;i<=n;++i) printf("%d ",rk[i]);
	// puts("");
	for(int i=1;i<=n;++i){
		upt(1,pre[rk[i]],abs(h[i]-cp[pre[rk[i]]].ht));
		upt(2,pre[pre[rk[i]]],abs(h[i]-cp[pre[pre[rk[i]]]].ht));
		upt(3,nxt[rk[i]],abs(h[i]-cp[nxt[rk[i]]].ht));
		upt(4,nxt[nxt[rk[i]]],abs(h[i]-cp[nxt[nxt[rk[i]]]].ht));
		sort(tmp_upt+1,tmp_upt+4+1);
		// printf("%d：\n",i);
		// for(int j=1;j<=4;++j){
			// printf("*tmp[%d]:记录 %d 号元素, rank 为 %d, 距离为 %d ;\n",j,cp[tmp_upt[j].id].id,tmp_upt[j].id,tmp_upt[j].ht);
		// }
		// puts("");
		nxb[i]=cp[tmp_upt[1].id].id,nxa[i]=cp[tmp_upt[2].id].id;
		del(rk[i]);
	}
	// for(int i=1;i<=n;++i){
		// printf("%d: nxb=%d nxa=%d\n",i,nxb[i],nxa[i]);
	// }
	// puts("");
}
inline void init_dp(){
	for(int i=1;i<=n;++i){
		f[i][0]=nxb[nxa[i]];
		A[i][0]=dis(i,nxa[i]);
		B[i][0]=dis(nxa[i],nxb[nxa[i]]);
		//printf("(%d,%d) A:%d,B:%d,To:%d; \n",i,1<<0,A[i][0],B[i][0],f[i][0]);
	}
	//A[i][j]=A[i][j-1]+A[f[i][j-1]][j-1];
	//B[i][j]=B[i][j-1]+B[f[i][j-1]][j-1];
	//f[i][j]=f[f[i][j-1]][j-1];
	lg2[1]=0,lg2[2]=1;
	for(int i=1;i<=n;++i) lg2[i]=lg2[i/2]+1;
	for(int j=1;j<=lg2[n]+1;++j){
		for(int i=1;i+(1<<j)-1<=n;++i){
			A[i][j]=A[i][j-1]+A[f[i][j-1]][j-1];
			B[i][j]=B[i][j-1]+B[f[i][j-1]][j-1];
			f[i][j]=f[f[i][j-1]][j-1];
			//printf("(%d,%d) A:%d,B:%d,To:%d; \n",i,1<<j,A[i][j],B[i][j],f[i][j]);
		}
	}
}
inline void work(){
	double as1=INF;
	int anscity=0;
	for(int i=1;i<=n;++i){
		auto as=solve(i,x0,0,0);
		double tmpans;
		//if(as.second==0&&as.first!=0) continue;
		tmpans=(double)as.first/(double)as.second;
		if(tmpans<as1||(equal(tmpans,as1)&&h[anscity]<h[i])){
			as1=tmpans;
			anscity=i;
		}
		//printf("*%d %d %lf\n",as.first,as.second,tmpans);
	}
	write(anscity),putchar('\n');
	for(int i=1;i<=m;++i){
		auto as=solve(s[i],x[i],0,0);
		write(as.first),putchar(' '),write(as.second),putchar('\n');
	}
}
signed main(){
	input();
	init_list();
	init_dp();
	work();
	return 0;
}

RT，WA on #2~#20，错误数据：

Input:

100
-26380932 -22679357 -21366282 -13457591 -4887741 -441955 -629701 -48147959 -44988819 -37008287 -34553007 -32822530 -27440485 -26059840 -86550374 -80274487 -75151274 -66571940 -58312018 -57173400 -55555547 -111966819 -104762441 -104608922 -99638934 -94599754 -93271105 -87375061 -128943461 -125372919 -123410299 -120968152 -120929135 -117800008 -112442669 -156065934 -154165771 -150118917 -146319072 -138129923 -133682386 -128784580 -185451666 -182685268 -177544527 -177041658 -175084161 -170619454 -164167578 -191341425 0 5619921 12969090 13988019 20386542 20775622 23031319 29731499 30210691 37940743 38101204 37597555 41663154 46851680 49215536 48414077 51683125 52580132 59145190 64803261 69924361 69319336 70891891 75970471 80855020 87204420 90887962 98109753 102829029 110901208 118467298 124039154 124687803 124126019 128076565 128878805 129973370 129956203 132552256 131774312 134229618 133502905 140711479 144743353 151543993 153134235 153874703 154049876 162175525 166135681
153905588
900
26 3798496
92 57499647
13 597012928

Correct Output:

30
0 0
25656963 6975813
130779664 65459978

My code's Output:

49
0 0
25656963 6975813
118693859 65459978

（另外此题 0/0 到底等于啥哇qwq）