C++ :

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define fir first
#define sec second
using namespace std;

const int N=100010;
typedef long long ll;
const ll INF=1LL<<40;
typedef pair<ll,ll> pii;
typedef set<pii>::iterator IT;
set<pii>s;
pii f[N][20];
int g[N][20],bg[N];
ll bf[N];
int n,k;
ll h[N];

void init() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&h[i]);
	s.insert(make_pair(INF,0));
	s.insert(make_pair(INF-1,0));
	s.insert(make_pair(-INF,0));
	s.insert(make_pair(-INF+1,0));
	for(int i=n;i;i--) {
		IT L,R,M;
		R=s.lower_bound(make_pair(h[i],0));
		L=R; --L;
		if(abs(h[i]-(R->fir))<abs(h[i]-(L->fir)))M=R;
		else M=L;
		
		bg[i]=M->sec;
		if(bg[i])bf[i]=abs(h[i]-(M->fir));
		
		if(M==R)++R;
		else --L;
		
		if(abs(h[i]-(R->fir))<abs(h[i]-(L->fir)))M=R;
		else M=L;
		
		g[i][0]=M->sec;
		if(g[i][0])f[i][0]=make_pair(abs(h[i]-(M->fir)),0);
		
		s.insert(make_pair(h[i],i));
	}
}

void table() {
	k=0;
	while((1<<(k+1))<n)k++;
	for(int i=1;i<=n;i++)
		if(g[i][0]&&bg[g[i][0]]) {
			f[i][1].fir=f[i][0].fir;
			f[i][1].sec=bf[g[i][0]];
			g[i][1]=bg[g[i][0]];
		}
	for(int j=2;j<=k;j++)
		for(int i=1;i<=n;i++)
			if(g[i][j-1]&&g[g[i][j-1]][j-1]) {
				f[i][j].fir=f[i][j-1].fir+f[g[i][j-1]][j-1].fir;
				f[i][j].sec=f[i][j-1].sec+f[g[i][j-1]][j-1].sec;
				g[i][j]=g[g[i][j-1]][j-1];
			}
}

pii go(int i,ll x) {
	pii res(0,0);
	for(int j=k;j>=0;j--)
		if(g[i][j]&&f[i][j].fir+f[i][j].sec<=x) {
			x-=f[i][j].fir+f[i][j].sec;
			res.fir+=f[i][j].fir;
			res.sec+=f[i][j].sec;
			i=g[i][j];
		}
	return res;
}

const double eps=1e-10;
int fcmp(pii a,pii b) {
	if(!a.sec&&!b.sec)return 0;
	if(!a.sec)return 1;
	if(!b.sec)return -1;
	double val=(double)a.fir/a.sec-(double)b.fir/b.sec;
	if(fabs(val)<eps)return 0;
	return val>0?1:-1;
} 

void work() {
	int s=1,m;
	ll x;
	scanf("%lld",&x);
	pii ans=go(1,x);
	for(int i=2;i<=n;i++) {
		pii res=go(i,x);
		int cmp=fcmp(res,ans);
		if(cmp==-1||(cmp==0&&h[i]>h[s])) {
			ans=res;
			s=i;
		}
	}
	printf("%d\n",s);
	scanf("%d",&m);
	while(m--) {
		scanf("%d%d",&s,&x);
		pii res=go(s,x);
		printf("%lld %lld\n",res.fir,res.sec);
	}
}

int main() {
	init();
	table();
	work();
	return 0;
}