#include "circus.h"
#include <bits/stdc++.h>
using namespace std;
#define a2 array <int,2>
#define a3 array <int,3>
const int INF=1e9+7;
map <int,int> best_f,best_r;
void init(int n, int m, int p[]){
sort(p,p+n);
vector <a2> d(n,{INF,INF});
priority_queue <a3> pq;
for(int i=0;i<n;i++) pq.push({{-(m-p[i]),i,0}});
while(!pq.empty()){
auto [d_u,u,c_u]=pq.top();
pq.pop();
d_u*=-1;
if(d[u][c_u]<=d_u) continue;
d[u][c_u]=d_u;
if(c_u==0 && u>0) pq.push({-(d_u+p[u]-p[u-1]),u-1,0});
else if(c_u==1 && u<n-1) pq.push({-(d_u+p[u+1]-p[u]),u+1,1});
int nxt=lower_bound(p,p+n,p[u]+d_u)-p;
if(nxt<n) pq.push({-(p[nxt]-p[u]),nxt,1});
nxt=upper_bound(p,p+n,p[u]-d_u)-p-1;
if(nxt>=0) pq.push({-(p[u]-p[nxt]),nxt,0});
}
for(int i=0;i<n;i++) d[i][0]=min(d[i][0],d[i][1]);
vector <int> ord(n);
iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](int x,int y)->bool{return p[x]-d[x][0]>p[y]-d[y][0];});
int best=INF;
for(int i:ord){
best=min(best,p[i]);
best_f[p[i]-d[i][0]]=best;
}
sort(ord.begin(),ord.end(),[&](int x,int y)->bool{return p[x]+d[x][0]<p[y]+d[y][0];});
best=-INF;
for(int i:ord){
best=max(best,p[i]);
best_r[p[i]+d[i][0]]=best;
}
best_f[m]=m;
}
int minLength(int d) {
int best=INF;
auto it=best_f.lower_bound(d);
if(it!=best_f.end()) best=min(best,(it->second)-d);
it=best_r.upper_bound(d);
if(it!=best_r.begin()){
it--;
best=min(best,d-(it->second));
}
return best;
}
