#include<set>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct node {
	int key,val;
	bool operator<(const node b)const {
        if(val!=b.val)
		    return val<b.val;
        else return key<b.key;
    }
};
int m,n,ans;
int s[100001],x[100001];
node A[100001],B[100001],h[100001],may[5];
int f[21][100001][2],fA[21][100001][2],fB[21][100001][2];
set<node> S;
node go(int sta,int step) {
    int a=0,b=0;
    for(int i=20;i>=0;i--)
        if(f[i][sta][0]&&a+b+fA[i][sta][0]+fB[i][sta][0]<=step) {
            a+=fA[i][sta][0];
            b+=fB[i][sta][0];
            sta=f[i][sta][0];
        }
    return (node){a,b};
}
bool cmp(node a,node b) {
    return a.val<b.val;
}
int main() {
	node temp;
	double max,quo;
	S.insert((node){0,-2147483647});
    S.insert((node){0,-2147483646});
    S.insert((node){0,2147483646});
    S.insert((node){0,2147483647});
	cin>>n;
    for(int i=1;i<=n;i++) {
	    cin>>h[i].val;
	    h[i].key=i;
	}
	cin>>x[0]>>m;
	for(int i=1;i<=m;i++)
	    cin>>s[i]>>x[i];
	for(int i=n;i>=1;i--) {
	    S.insert(h[i]);
        may[1]=*--S.lower_bound(h[i]);
        may[2]=*--S.lower_bound(may[1]);
        may[3]=*S.upper_bound(h[i]);
        may[4]=*S.upper_bound(may[3]);
        for(int j=1;j<=4;j++)
		    may[j].val=abs(may[j].val-h[i].val);
        sort(may+1,may+5,cmp);
        A[i]=may[2];
        B[i]=may[1];
	}
	for(int i=1;i<=n;i++) {
        f[0][i][0]=A[i].key;
        f[0][i][1]=B[i].key;
    }
    for(int i=1;i<=20;i++)
    	for(int j=1;j<=n;j++)
	        if(j+(1<<i)<=n)
		        for(int k=0;k<=1;k++)
			        if(i==1)
				        f[1][j][k]=f[0][f[0][j][k]][1-k];
				    else
				        f[i][j][k]=f[i-1][f[i-1][j][k]][k];
	for(int i=1;i<=n;i++) {
        fA[0][i][0]=A[i].val;
        fA[0][i][1]=0;
    }
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
	        if(j+(1<<i)<=n)
		        for(int k=0;k<=1;k++)
                    if(i==1)
                        fA[1][j][k]=fA[0][j][k]+fA[0][f[0][j][k]][1-k];
                    else
					    fA[i][j][k]=fA[i-1][j][k]+fA[i-1][f[i-1][j][k]][k];
	for(int i=1;i<=n;i++) {
        fB[0][i][0]=0;
        fB[0][i][1]=B[i].val;
    }
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
	        if(j+(1<<i)<=n)
		        for(int k=0;k<=1;k++)
				    if(i==1)
                        fB[1][j][k]=fB[0][j][k]+fB[0][f[0][j][k]][1-k];
                    else
					    fB[i][j][k]=fB[i-1][j][k]+fB[i-1][f[i-1][j][k]][k];
	max=2000000000;
	for(int i=1;i<=n;i++) {
		temp=go(i,x[0]);
		if(temp.val==0)
		    continue;
        quo=(double)temp.key/(double)temp.val;
        if(quo<max||quo==0) {
        	max=quo;
        	ans=i;
		}
	}
	if(ans!=0)
	    cout<<ans;
	else
	    cout<<n;
	for(int i=1;i<=m;i++) {
		cout<<endl;
		temp=go(s[i],x[i]);
        cout<<temp.key<<' '<<temp.val;
	}	
	return 0;
}

95pts

但

S.insert((node){0,-2147483647});
S.insert((node){0,-2147483646});
S.insert((node){0,2147483646});
S.insert((node){0,2147483647});

改成

S.insert((node){0,-2000000002});
S.insert((node){0,-2000000001});
S.insert((node){0,2000000001});
S.insert((node){0,2000000002});

则AC

这是为什么啊？？？