模拟赛做到的题，赛后看了 Y2hlbnlpa2Fp 的题解，感觉没讲清楚，这里做下补充，提供自己的理解。

基本思路：

对每个 \(A_i\) 的答案进行预处理，对于每个询问，只需要找到第一个到达的景点即可。

那么如何预处理每个点的答案呢？有一条很重要的性质：最多转向 \(\log{X}\) 次。

要证明这个结论，先放上一张图：

设第 \(k\) 段路径长度为 \(L\)，从图中可以看出，\(L_{k}\geq 2\times L_{k-1}\)，因为 \(1 \leq L_k\leq X\)，可以推得 \(k\leq \log{X}\)。

证明了这个结论，我们就可以在 \(\mathcal{O}(n^2\log{n})\) 的时间暴力走一遍预处理出答案，运用ST表倍增可以优化到 \(\mathcal{O}(n\log^2{n})\)。

对于每个询问，二分找到第一个到达的景点，直接输出对应的答案即可。

整体复杂度 \(\mathcal{O}(n\log^2{n}+q\log{N})\)。

注释很详细，写在代码里，注释掉的代码是对 Y2hlbnlpa2Fp 题解的改进。

\(Code\)

#include<bits/stdc++.h>//MoSheng
using namespace std;
#define ll long long
#define ul unsigned long long
#define db double
#define il inline
#define re register
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f//ll范围下LINF，够大 
#define int ll//要开longlong 
#define F(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define DF(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define G(i,u) for(int (i)=head[u];(i);(i)=nxt[(i)])
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x*f;}
const int N=200010;
int n;
int pos[N],ans[N];
int stl[N][25],str[N][25];
signed main()
{
	n=read();
	F(i,1,n) pos[i]=read();
	pos[0]=-LINF;//边界处理I
	pos[n+1]=LINF;//一定要开7f^4或3f^8，1e9范围下3f^4太小 
//	if(n==1)//特判？其实没必要，因为有边界处理 
//	{
//		int q=read();
//		F(i,1,q)
//		{
//			int loc=read();
//			printf("%lld\n",abs(loc-pos[1]));
//		}
//		return 0;
//	}
	F(i,1,n-1) stl[i][0]=pos[i]-(pos[i+1]-pos[i]);//该点向右移动的距离在左边的坐标映射，便于与左节点距离比较 
	stl[n][0]=-LINF;//边界处理II
	F(i,2,n) str[i][0]=pos[i]+(pos[i]-pos[i-1]);//该点向左移动的距离在右边的坐标映射，便于与右节点距离比较 
	str[1][0]=LINF;
	F(k,1,20)
	{
		F(i,1,n)
			if(i+(1<<(k-1))<=n)
				stl[i][k]=min(stl[i][k-1],stl[i+(1<<(k-1))][k-1]);//过程中最远的一次能满足就一定满足全过程，所以取极值 
//			else//不满足则说明扩展到底了，不用继续拓展。但其实这步不需要，因为处理时不满足时会continue 
//				stl[i][k]=stl[i][k-1];
		F(i,1,n)//DF(i,n,1)//正反皆可 
			if(i-(1<<(k-1))>=1)
				str[i][k]=max(str[i][k-1],str[i-(1<<(k-1))][k-1]);
//			else
//				str[i][k]=str[i][k-1];
	}
	F(i,1,n)
	{
		int l=i,r=i,dir=0,now=i;//l和r分别表示左右两边走到的最远点 
		if(pos[i]-pos[i-1]<=pos[i+1]-pos[i]) dir=0;//判断开始时移动方向，0为左，1为右  
		else dir=1; 
		while(1<l||r<n)//还有没走的点 
		{
			if(dir==0)//先向左再向右转 
			{
				now=l;
				now--;//转完向至少走一步，提前走掉 
				DF(k,20,0)//倍增经典倒序，向左走到不能走 
				{
					if(now-(1<<k)<1) continue;//无法往左移动1<<k次就跳过，注意不能带= 
					if(str[now][k]<=pos[r+1]) now-=(1<<k);//向左走的距离更近就走，注意这里now不需要-1，因为我们已经提前走过一步了 
				}
//				now--;//这一步与now的-1一样，其实就是上一次转向后至少要走的那一步，我们在转向后立刻处理就不需要（不能加）这一步 
				ans[i]+=pos[r]-pos[now];
				l=now;
				dir=1;//记得转向 
			}
			else// if(dir==1)//先向右再向左转 
			{
				now=r;
				now++;//转完向至少走一步，提前走掉 
				DF(k,20,0)//倍增经典倒序，向右走到不能走 
				{
					if(now+(1<<k)>n) continue;//无法往右移动1<<k次就跳过，注意不能带=
					if(stl[now][k]>pos[l-1]) now+=(1<<k);//向右走的距离更近就走，与dir==0的情况同理，now不需要+1 
				} 
//				now++;//与dir==0的情况同理，这步不加 
				ans[i]+=pos[now]-pos[l];
				r=now;
				dir=0;//记得转向 
			}
		}
	}
	int q=read();
	F(i,1,q)
	{
		int loc=read();
		int R=upper_bound(pos+1,pos+n+1,loc)-pos;//找右边最近点，lower_bound和upper_bound都可 
		int L=R-1;//左边最近点 
		if(loc-pos[L]<=pos[R]-loc) printf("%lld\n",loc-pos[L]+ans[L]);
		else printf("%lld\n",pos[R]-loc+ans[R]);
	}
	return 0;
}