如果我们一开始的位置不是 \(x_i\)，先移动到 \(x\) 上的最近的点，然后我们开始讨论从这个点开始辐射全 \(n\) 个点。
首先，我们发现，我们已经访问过的所有位置一定是一段连续的区间。那么我们可以很快找到 \(N\le 2000\) 的做法，我们可以区间 \(dp\)，设 \(dp_{l,r,s}\) 为当前区间为 \([l,r]\)，当前人在 \(l/r\) 的路程。
我们发现，我们还可以通过 \(Q=1\) 的做法，因为我们可以暴力模拟人的前进路线，使用 \(map\) 或者链表做到 \(O(n\log n)\) 或者 \(O(n)\)。
接着我们考虑观察性质，如果我们目前在区间的左边，我们很明显往左走直到当前点 \(i\) 满足 \(x_i-x_{i-1}>x_{r+1}-x_i\)。也就是当前 \([l,r]\) 可以直接拓展到 \([i,r]\) 然后到右边去。在右边同理。
优化
考虑优化。我们发现，在左边，是要找到最近的点 \(i\) 满足 \(2x_i-x_{i-1}>x_{r+1}\),在右边，是要找到最近的点 \(i\) 满足 \(2x_i-x_{i+1}\le x_{l-1}\)。很明显，可以用两棵主席树维护。我们就能做到 \(O(n\log n)\) 预处理，\(O(\log n)\) 查询下一次转向的位置。
同时，我们还可以记忆化一下从每个 \(x_i\) 开始的答案，如果这里搜索过就可以直接输出。
如果我们直接这样把程序写出来，我们发现就可以通过了，而且很快，这是为什么呢？
复杂度分析
我们发现，如果我们在左端转向，意味着 \(x_l-x_{l-1}>x_{r+1}-x_l\)，在右端转向，意味着 \(x_{r+1}-x_r\ge x_{r}-x_{l-1}\)。而这个做法的实际最大复杂度就是从 \(1\sim n\) 所有点开始跑一遍的转向次数总和。
我们发现，想要转向，对于区间本身的要求是及其苛刻的。它要求区间某边一次的增量大于整个区间的增量总和。
而如果我们把增量 \(s_i=x_i-x_{i-1}\) 列出来，那么要求 \(\sum s_i\le 10^9\)，一个区间 \([l,r]\) 能贡献意味着 \(s_{r+1}\ge\sum_{i\in(l,r]}s_i\) 或者 \(s_l\gt \sum_{i\in(l,r]}s_i\)。
假设从 \(1\) 开始经历了 \(k\) 次转向，那么每次转向的 \(s_i\) 都需要大于 \(\sum_{j\lt i} s_j\)。即设为等于，则有 \(s_j=\sum_{j\lt i} s_j\)。设 \(s_0=1\)，则 \(s_j=2^{j-1}\)。我们简单的分析出它是随 \(k\) 指数增长的。但是 \(s_j\) 最多只有 \(10^9\)，所以从一个位置出发所能达到的最多转向次数是 \(\log 10^9=30\) 级别的。所以，我们的算法复杂度是 \(O(n\log n\log x)\)。足以通过。
int n,x[200005],y[200005],q,s,l,r;
ll ans[200005];
ll v[600005],m;
class pst{
private:
int ans[10000005];
int ls[10000005],rs[10000005],cnt,Len;
int root[200005],Ti;
inline void Init(int &i,int l,int r){
i=++cnt,ans[i]=1e9;
if(l==r)return;
int mid=(l+r)>>1;
Init(ls[i],l,mid);
Init(rs[i],mid+1,r);
}
inline void Modify(int &i,int his,int x,int v,int l,int r){
i=++cnt;
ans[i]=min(ans[his],v);
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid){
rs[i]=rs[his];
Modify(ls[i],ls[his],x,v,l,mid);
}else{
ls[i]=ls[his];
Modify(rs[i],rs[his],x,v,mid+1,r);
}
}
inline ll Query(int i,int L,int R,int l,int r){
if(!i)return 1e9;
if(L<=l&&r<=R)return ans[i];
int mid=(l+r)>>1;
ll res=1e9;
if(ls[i]&&L<=mid)res=min(res,Query(ls[i],L,R,l,mid));
if(rs[i]&&R>mid)res=min(res,Query(rs[i],L,R,mid+1,r));
return res;
}
public:
inline void init(int len){
Len=len;
Init(root[0],1,len);
}
inline void modify(int id,int lst,int x,int v){
Modify(root[id],root[lst],x,v,1,Len);
}
inline ll query(int id,int l,int r){
if(l>r)return 1e9;
return Query(root[id],l,r,1,Len);
}
}ta,tb;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;rp(i,n)cin>>x[i];
cin>>q;x[0]=-2e9,x[n+1]=2e9;
rp(i,n)ans[i]=-1;
rp(i,n)v[++m]=x[i];v[++m]=-1e18,v[++m]=1e18;
rp(i,n)v[++m]=2*x[i]-x[i-1];
rp(i,n)v[++m]=2*x[i]-x[i+1];
sort(v+1,v+1+m);
m=unique(v+1,v+1+m)-v-1;
ta.init(m);tb.init(m);
rp(i,n)y[i]=lower_bound(v+1,v+1+m,x[i])-v;y[0]=0,y[n+1]=m+1;
rep(i,1,n)ta.modify(i,i-1,lower_bound(v+1,v+1+m,2*x[i]-x[i-1])-v,-i);
per(i,1,n)tb.modify(i,(i+1)%(n+1),lower_bound(v+1,v+1+m,2*x[i]-x[i+1])-v,i);
if(n==1){
rp(_,q){
cin>>s;
cout<<abs(s-x[1])<<endl;
}
return 0;
}
rp(_,q){
cin>>s;
int pre=lower_bound(x+1,x+1+n,s)-x-1;
int nxt=lower_bound(x+1,x+1+n,s)-x;
if(abs(s-x[pre])<=abs(s-x[nxt]))l=r=pre;
else l=r=nxt;int cur=0;int ori=l;
if(ans[l]!=-1){
cout<<abs(x[l]-s)+ans[l]<<endl;
continue;
}ll res=0;
if(x[l]-x[l-1]<=x[r+1]-x[r])res+=x[l]-x[l-1],l--,cur=0;
else res+=x[r+1]-x[r],r++,cur=1;
while(l>1||r<n){
if(cur){
int gt=tb.query(r,1,y[l-1]);
if(gt==1e9)gt=n;
res+=x[gt]-x[r],r=gt,cur=0;
if(l>1)l--,cur=0,res+=x[r]-x[l];
}else{
int gt=ta.query(l,y[r+1]+1,m);
if(gt==1e9)gt=1;
else gt=-gt;
res+=x[l]-x[gt],l=gt,cur=1;
if(r<n)r++,cur=1,res+=x[r]-x[l];
}
}
ans[ori]=res;
cout<<abs(x[ori]-s)+ans[ori]<<endl;
}
return 0;
}
//Crayan_r