记录编号	196831	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]开车旅行	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	3.713 s
提交时间	2015-10-22 19:33:23	内存使用	101.79 MiB

#define MAXN 100010UL
#define MAXS 22UL
#define inf (1e14)
#define eps (1e-7)

#define ll long long

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef std::pair<ll,ll> Rtn;

struct Node{
	Node *left,*right;
	ll val,fix;
	Node(){left=right=NULL;return;}
}*root;
ll height[MAXN],x0,n,m,now_pos,pre[2][MAXN][MAXS][3],limit;
inline ll ABS(ll a){return a>0?a:-a;}
inline ll dis(ll i,ll j){
	if(j==-1||i==-1) return (ll)inf;
	return ABS(height[i]-height[j]);
}

inline void Rturn(Node *&a){
	Node *b=a->left;
	a->left=b->right;
	b->right=a;
	a=b;return;
}

inline void Lturn(Node *&a){
	Node *b=a->right;
	a->right=b->left;
	b->left=a;
	a=b;return;
}

inline void Insert(Node *&p,ll val){
	if(!p){
		p=new Node();p->val=val;
		p->fix=rand();return;
	}
	if(height[val]<(height[p->val])){
		Insert(p->left,val);
		if((p->left->fix)<(p->fix)) Rturn(p);
	}
	else{
		Insert(p->right,val);
		if((p->right->fix)<(p->fix)) Lturn(p);
	}
	return;
}

inline ll Find_Smaller(Node *p,ll val){
	if(!p) return -1;
	if(height[p->val]<height[val]){
		int tmp=Find_Smaller(p->right,val);
		if(tmp!=-1) return tmp;
		return p->val;
	}
	return Find_Smaller(p->left,val);
}

inline ll Find_Bigger(Node *p,ll val){
	if(!p) return -1;
	if(height[p->val]>height[val]){
		int tmp=Find_Bigger(p->left,val);
		if(tmp!=-1) return tmp;
		return p->val;
	}
	return Find_Bigger(p->right,val);
}

inline bool comp(ll a,ll b){
	if(a==-1) return false;
	if(b==-1) return true;
	ll d1=dis(now_pos,a),d2=dis(now_pos,b);
	if(d1==d2) return height[a]<height[b];
	return d1<d2;
}

//pre i,j,k,l
/*
i==0 from A
i==1 from B
j 2^k
l==0 where
l==1 A
l==2 B
*/
//f0 f1 now f2 f3

inline Rtn Cal(ll s,ll x){
	Rtn Ans;ll Ans1=0,Ans2=0,last=-1;
	for(;;){
		bool flag=false;
		//printf("%lld->",s);
		for(ll i=limit;i>=0;i--) if((pre[0][s][i][0]!=-1)&&(pre[0][s][i][1]+pre[0][s][i][2]<=x)){
			flag=true;//printf("%lld\n",i);
			Ans1+=pre[0][s][i][1],Ans2+=pre[0][s][i][2],x-=pre[0][s][i][1]+pre[0][s][i][2],s=pre[0][s][i][0];
			last=i;break;
		}
		if(!flag){
			if(last==0&&pre[1][s][0][0]!=-1){
                //printf("_>%lld\n",pre[1][s][0][0]);
				if(x>=pre[1][s][0][1]+pre[1][s][0][2]){
					Ans1+=pre[1][s][0][1],Ans2+=pre[1][s][0][2];
				}
			}
			break;
		}
	}//puts("");
	Ans.first=Ans1,Ans.second=Ans2;
	return Ans;
}

inline void PreWork(){
	for(ll i=n,f[4];i>0;i--){
		memset(f,-1,sizeof(f));
		f[1]=Find_Bigger(root,i);
		if(f[1]!=-1) f[0]=Find_Bigger(root,f[1]);
		f[2]=Find_Smaller(root,i);
		if(f[2]!=-1) f[3]=Find_Smaller(root,f[2]);
		now_pos=i;std::sort(f,f+4,comp);
		pre[0][i][0][0]=f[1];
		pre[0][i][0][1]=dis(i,f[1]);
		pre[0][i][0][2]=0;
		pre[1][i][0][0]=f[0];
		pre[1][i][0][1]=0;
		pre[1][i][0][2]=dis(i,f[0]);
	// 	if(i==3) printf("%lld %lld\n",pre[0][i][0][0],pre[1][i][0][0]);
		Insert(root,i);
	}
	scanf("%lld%lld",&x0,&m);
	for(int j=1,arr;(1<<j)<=n;j++){
		limit=j;
		for(int i=1;i<=n;i++){
			//updating pre[mask][i][j][l]
			if(j==1){
				if(pre[0][i][j-1][0]==-1){
					pre[0][i][j][0]=-1;
					pre[0][i][j][1]=pre[0][i][j][2]=inf;
				}
				else{
					arr=pre[0][i][j-1][0];
					pre[0][i][j][0]=pre[1][arr][j-1][0];
					pre[0][i][j][1]=pre[0][i][j-1][1]+pre[1][arr][j-1][1];
					pre[0][i][j][2]=pre[0][i][j-1][2]+pre[1][arr][j-1][2];
				}
			}
			else{
				if(pre[0][i][j-1][0]==-1){
					pre[0][i][j][0]=-1;
					pre[0][i][j][1]=pre[0][i][j][2]=inf;
				}
				else{
					arr=pre[0][i][j-1][0];
					pre[0][i][j][0]=pre[0][arr][j-1][0];
					pre[0][i][j][1]=pre[0][i][j-1][1]+pre[0][arr][j-1][1];
					pre[0][i][j][2]=pre[0][i][j-1][2]+pre[0][arr][j-1][2];
				}
			}
		}
	}
	ll best_=1;double comp_Ans=inf;
	for(ll i=1;i<=n;i++){
		Rtn Ans=Cal(i,x0);
		double temp_rs=(Ans.second==0)?((double)(inf)):((double)((double)Ans.first/(double)Ans.second));
		if(comp_Ans>temp_rs) comp_Ans=temp_rs,best_=i;
	}
	printf("%lld\n",best_);
	return;
}

inline void Work(){
	ll s,x;
	scanf("%lld%lld",&s,&x);
	Rtn Ans=Cal(s,x);printf("%lld %lld",Ans.first,Ans.second);
	return;
}

int main(){
	freopen("drive.in","r",stdin);freopen("drive.out","w",stdout);
	scanf("%lld",&n);memset(pre,-1,sizeof(pre));
	for(ll i=1;i<=n;i++) scanf("%lld",&height[i]);
	PreWork();for(ll i=1;i<=m;i++,puts("")) Work();
	return 0;
}