C++ :

#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXN 100100
#define INF 0x7fffffff
using namespace std;
int n,m,en[MAXN],s[5];
int find(int x){
	int l=1,r=n,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(en[mid]<=x){
			if(en[mid+1]>=x) return mid;
			else l=mid+1;
		}
		else r=mid-1;
	}
	return l;
}
int my_abs(int x){
	if(x>=0) return x;
	return -x;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	   scanf("%d",&en[i]);
	sort(en+1,en+n+1);
	en[n+1]=INF;
	en[0]=-INF;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if(x1>0&&x2>0&&y1>0&&y2>0||x1<0&&x2<0&&y1<0&&y2<0){
			int x=x1-x2,y=y1-y2;
	        x=my_abs(x);
	        y=my_abs(y);
	       printf("%d\n",x+y);
		}
		else{
			s[1]=find(x1);s[2]=s[1]+1;
			s[3]=find(x2);s[4]=s[3]+1;
			int my_min=INF;
			int yy=my_abs(y1-y2);
			for(int j=1;j<=4;j++){
				int xx1=my_abs(x1-en[s[j]]),xx2=my_abs(x2-en[s[j]]);
				int tmp=xx1+xx2+yy;
				if(tmp>=yy&&my_min>tmp)
				   my_min=tmp;
			}
			printf("%d\n",my_min);
		}
	}
	return 0;
}