#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,m,Go[2005][2],ansl;
LL a[2005],x0,Dist[2005][2005],Min[2005],Second[2005],ans[2]= {1,10000000000};
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
memset(Min,0x7f,sizeof(Min));
memset(Second,0x7f,sizeof(Second));
for(int i=1; i<=n; i++) {
int Minl=0,Secondl=0;
for(int j=i+1; j<=n; j++) {
Dist[i][j]=abs(a[i]-a[j]);
if(Dist[i][j]<Min[i]||(Dist[i][j]==Min[i]&&a[j]<a[Minl])) {
Second[i]=Min[i];
Secondl=Minl;
Min[i]=Dist[i][j];
Minl=j;
} else if(Dist[i][j]<Second[i]||(Dist[i][j]==Second[i]&&a[j]<a[Secondl])) {
Second[i]=Dist[i][j];
Secondl=j;
}
}
Go[i][0]=Minl;
Go[i][1]=Secondl;
}
x0=Get_Int();
for(int i=1; i<=n; i++) { //从i开始
LL Now=i,dist=0,chose=1,sum[2]= {0};
while(Go[Now][chose]&&dist+Dist[Now][Go[Now][chose]]<=x0) {
dist+=Dist[Now][Go[Now][chose]];
sum[chose]+=Dist[Now][Go[Now][chose]];
Now=Go[Now][chose];
chose^=1;
}
if(sum[0]!=0&&(ans[1]*sum[0]>ans[0]*sum[1]||(ans[1]*sum[0]==ans[0]*sum[1]&&a[i]>a[ansl]))) {
ans[1]=sum[1];
ans[0]=sum[0];
ansl=i;
}
}
printf("%d\n",ansl);
m=Get_Int();
while(m--) {
LL Now=Get_Int(),x=Get_Int(),dist=0,chose=1,sum[2]= {0};
while(Go[Now][chose]&&dist+Dist[Now][Go[Now][chose]]<=x) {
dist+=Dist[Now][Go[Now][chose]];
sum[chose]+=Dist[Now][Go[Now][chose]];
Now=Go[Now][chose];
chose^=1;
}
printf("%lld %lld\n",sum[1],sum[0]);
}
return 0;
}

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
int n,m,Go[maxn][2],ansl,Left[maxn],Right[maxn],p[maxn][25];
LL x0,a[maxn],ans[2]= {1,10000000000},Dist[maxn][2],DistA[maxn][25],DistB[maxn][25];
struct City {
int height,pos;
bool operator < (const City& b) const {
return height<b.height;
}
} b[maxn];
LL dist(int x,int y) {
return abs(a[x]-a[y]);
}
void Sparse_Table() {
for(int i=1; i<n; i++) {
p[i][0]=Go[Go[i][1]][0];
DistA[i][0]=Dist[i][1];
DistB[i][0]=Dist[Go[i][1]][0];
}
for(int j=1; j<=log2(n); j++)
for(int i=1; i<=n; i++) {
p[i][j]=p[p[i][j-1]][j-1];
if(!p[i][j])continue;
DistA[i][j]=DistA[i][j-1]+DistA[p[i][j-1]][j-1];
DistB[i][j]=DistB[i][j-1]+DistB[p[i][j-1]][j-1];
}
}
void Jump(int Now,LL x,LL* sum) {
int k=log2(n);
LL tot=0;
for(int i=k; i>=0; i--)
if(p[Now][i]&&tot+DistA[Now][i]+DistB[Now][i]<=x) {
tot+=DistA[Now][i]+DistB[Now][i];
sum[1]+=DistA[Now][i];
sum[0]+=DistB[Now][i];
Now=p[Now][i];
}
if(tot+DistA[Now][0]<=x) {
tot+=DistA[Now][0];
sum[1]+=DistA[Now][0];
Now=Go[Now][1];
}
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
b[i].height=a[i];
b[i].pos=i;
}
sort(b+1,b+n+1);
for(int i=1; i<=n; i++) {
Left[b[i].pos]=b[i-1].pos;
Right[b[i].pos]=b[i+1].pos;
}
for(int i=1; i<=n; i++) { //双向链表处理最近次近
LL Min=1e15,Second=1e15;
int Minl=0,Secondl=0;
if(Left[i])Min=min(Min,dist(i,Left[i])),Minl=Left[i];
if(Left[Left[i]]&&dist(i,Left[Left[i]])<Second)Second=dist(i,Left[Left[i]]),Secondl=Left[Left[i]];
if(Right[i]&&dist(i,Right[i])<Min) {
Second=Min;
Secondl=Minl;
Min=dist(i,Right[i]);
Minl=Right[i];
} else if(Right[i]&&dist(i,Right[i])<Second)Second=dist(i,Right[i]),Secondl=Right[i];
if(Right[Right[i]]&&dist(i,Right[Right[i]])<Second)Second=dist(i,Right[Right[i]]),Secondl=Right[Right[i]];
Go[i][0]=Minl;
Go[i][1]=Secondl;
Dist[i][0]=Min;
Dist[i][1]=Second;
if(Right[i])Left[Right[i]]=Left[i];
if(Left[i])Right[Left[i]]=Right[i];
}
Sparse_Table();
x0=Get_Int();
for(int i=1; i<=n; i++) { //从i开始
LL sum[2]= {0,0};
Jump(i,x0,sum);
if(sum[0]!=0&&(ans[1]*sum[0]>ans[0]*sum[1]||(ans[1]*sum[0]==ans[0]*sum[1]&&a[i]>a[ansl]))) {
ans[1]=sum[1];
ans[0]=sum[0];
ansl=i;
}
}
printf("%d\n",ansl);
m=Get_Int();
while(m--) {
LL sum[2]= {0,0},Now=Get_Int(),x=Get_Int();
Jump(Now,x,sum);
printf("%lld %lld\n",sum[1],sum[0]);
}
return 0;
}

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
int n,m,Go[maxn][2],ansl,Left[maxn],Right[maxn],p[maxn][25];
LL x0,a[maxn],ans[2]= {1,10000000000},Dist[maxn][2],DistA[maxn][25],DistB[maxn][25];
struct City {
int height,pos;
bool operator < (const City& b) const {
return height<b.height;
}
} b[maxn];
LL dist(int x,int y) {
return abs(a[x]-a[y]);
}
void Sparse_Table() {
for(int i=1; i<n; i++) {
p[i][0]=Go[Go[i][1]][0];
DistA[i][0]=Dist[i][1];
DistB[i][0]=Dist[Go[i][1]][0];
}
for(int j=1; j<=log2(n); j++)
for(int i=1; i<=n; i++) {
p[i][j]=p[p[i][j-1]][j-1];
if(!p[i][j])continue;
DistA[i][j]=DistA[i][j-1]+DistA[p[i][j-1]][j-1];
DistB[i][j]=DistB[i][j-1]+DistB[p[i][j-1]][j-1];
}
}
void Jump(int Now,LL x,LL* sum) {
int k=log2(n);
LL tot=0;
for(int i=k; i>=0; i--)
if(p[Now][i]&&tot+DistA[Now][i]+DistB[Now][i]<=x) {
tot+=DistA[Now][i]+DistB[Now][i];
sum[1]+=DistA[Now][i];
sum[0]+=DistB[Now][i];
Now=p[Now][i];
}
if(tot+DistA[Now][0]<=x) {
tot+=DistA[Now][0];
sum[1]+=DistA[Now][0];
Now=Go[Now][1];
}
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
b[i].height=a[i];
b[i].pos=i;
}
sort(b+1,b+n+1);
for(int i=1; i<=n; i++) {
Left[b[i].pos]=b[i-1].pos;
Right[b[i].pos]=b[i+1].pos;
}
for(int i=1; i<=n; i++) { //双向链表处理最近次近
LL Min=1e15,Second=1e15;
int Minl=0,Secondl=0;
if(Left[i])Min=min(Min,dist(i,Left[i])),Minl=Left[i];
if(Left[Left[i]]&&dist(i,Left[Left[i]])<Second)Second=dist(i,Left[Left[i]]),Secondl=Left[Left[i]];
if(Right[i]&&dist(i,Right[i])<Min) {
Second=Min;
Secondl=Minl;
Min=dist(i,Right[i]);
Minl=Right[i];
} else if(Right[i]&&dist(i,Right[i])<Second)Second=dist(i,Right[i]),Secondl=Right[i];
if(Right[Right[i]]&&dist(i,Right[Right[i]])<Second)Second=dist(i,Right[Right[i]]),Secondl=Right[Right[i]];
Go[i][0]=Minl;
Go[i][1]=Secondl;
Dist[i][0]=Min;
Dist[i][1]=Second;
if(Right[i])Left[Right[i]]=Left[i];
if(Left[i])Right[Left[i]]=Right[i];
}
Sparse_Table();
x0=Get_Int();
for(int i=1; i<=n; i++) { //从i开始
LL sum[2]= {0,0};
Jump(i,x0,sum);
if(sum[0]!=0&&(ans[1]*sum[0]>ans[0]*sum[1]||(ans[1]*sum[0]==ans[0]*sum[1]&&a[i]>a[ansl]))) {
ans[1]=sum[1];
ans[0]=sum[0];
ansl=i;
}
}
printf("%d\n",ansl);
m=Get_Int();
while(m--) {
LL sum[2]= {0,0},Now=Get_Int(),x=Get_Int();
Jump(Now,x,sum);
printf("%lld %lld\n",sum[1],sum[0]);
}
return 0;
}

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
int n,m,Go[maxn][2],ansl,Left[maxn],Right[maxn],p[maxn][25];
LL x0,a[maxn],ans[2]= {1,10000000000},Dist[maxn][2],DistA[maxn][25],DistB[maxn][25];
struct City {
int height,pos;
bool operator < (const City& b) const {
return height<b.height;
}
} b[maxn];
LL dist(int x,int y) {
return abs(a[x]-a[y]);
}
void Sparse_Table() {
for(int i=1; i<n; i++) {
p[i][0]=Go[Go[i][1]][0];
DistA[i][0]=Dist[i][1];
DistB[i][0]=Dist[Go[i][1]][0];
}
for(int j=1; j<=log2(n); j++)
for(int i=1; i<=n; i++) {
p[i][j]=p[p[i][j-1]][j-1];
if(!p[i][j])continue;
DistA[i][j]=DistA[i][j-1]+DistA[p[i][j-1]][j-1];
DistB[i][j]=DistB[i][j-1]+DistB[p[i][j-1]][j-1];
}
}
void Jump(int Now,LL x,LL* sum) {
int k=log2(n);
LL tot=0;
for(int i=k; i>=0; i--)
if(p[Now][i]&&tot+DistA[Now][i]+DistB[Now][i]<=x) {
tot+=DistA[Now][i]+DistB[Now][i];
sum[1]+=DistA[Now][i];
sum[0]+=DistB[Now][i];
Now=p[Now][i];
}
if(tot+DistA[Now][0]<=x) {
tot+=DistA[Now][0];
sum[1]+=DistA[Now][0];
Now=Go[Now][1];
}
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
b[i].height=a[i];
b[i].pos=i;
}
sort(b+1,b+n+1);
for(int i=1; i<=n; i++) {
Left[b[i].pos]=b[i-1].pos;
Right[b[i].pos]=b[i+1].pos;
}
for(int i=1; i<=n; i++) { //双向链表处理最近次近
LL Min=1e15,Second=1e15;
int Minl=0,Secondl=0;
if(Left[i])Min=min(Min,dist(i,Left[i])),Minl=Left[i];
if(Left[Left[i]]&&dist(i,Left[Left[i]])<Second)Second=dist(i,Left[Left[i]]),Secondl=Left[Left[i]];
if(Right[i]&&dist(i,Right[i])<Min) {
Second=Min;
Secondl=Minl;
Min=dist(i,Right[i]);
Minl=Right[i];
} else if(Right[i]&&dist(i,Right[i])<Second)Second=dist(i,Right[i]),Secondl=Right[i];
if(Right[Right[i]]&&dist(i,Right[Right[i]])<Second)Second=dist(i,Right[Right[i]]),Secondl=Right[Right[i]];
Go[i][0]=Minl;
Go[i][1]=Secondl;
Dist[i][0]=Min;
Dist[i][1]=Second;
if(Right[i])Left[Right[i]]=Left[i];
if(Left[i])Right[Left[i]]=Right[i];
}
Sparse_Table();
x0=Get_Int();
for(int i=1; i<=n; i++) { //从i开始
LL sum[2]= {0,0};
Jump(i,x0,sum);
if(sum[0]!=0&&(ans[1]*sum[0]>ans[0]*sum[1]||(ans[1]*sum[0]==ans[0]*sum[1]&&a[i]>a[ansl]))) {
ans[1]=sum[1];
ans[0]=sum[0];
ansl=i;
}
}
printf("%d\n",ansl);
m=Get_Int();
while(m--) {
LL sum[2]= {0,0},Now=Get_Int(),x=Get_Int();
Jump(Now,x,sum);
printf("%lld %lld\n",sum[1],sum[0]);
}
return 0;
}