#include <bits/stdc++.h>
using ll = long long;
constexpr int INF = 1e9;
std::map<int, int> best_f, best_r;
void init(int n, int m, int p[]) {
std::sort(p, p + n);
// dist[i] = {dist from left, dist from right}
std::vector<std::array<int, 2>> dist(n, {INF, INF});
std::priority_queue<std::array<int, 3>> pq;
for (int i = 0; i < n; i++) {
// initialize left dist with jump from m
pq.push({-(m - p[i]), i, 0});
}
while (!pq.empty()) {
auto [t, u, f] = pq.top();
pq.pop();
t *= -1;
if (dist[u][f] <= t) continue;
dist[u][f] = t;
// use 'ghost edge'
if (f == 0 && u > 0) {
pq.push({-(t + p[u] - p[u - 1]), u - 1, 0});
} else if (f == 1 && u + 1 < n) {
pq.push({-(t + p[u + 1] - p[u]), u + 1, 1});
}
// jump forward by t
int nxt = std::lower_bound(p, p + n, p[u] + t) - p;
if (nxt < n) {
pq.push({-(p[nxt] - p[u]), nxt, 1});
}
// jump backwards by t
nxt = std::upper_bound(p, p + n, p[u] - t) - p - 1;
if (nxt >= 0) {
pq.push({-(p[u] - p[nxt]), nxt, 0});
}
}
for (int i = 0; i < n; i++) {
dist[i][0] = std::min(dist[i][0], dist[i][1]);
}
std::vector<int> ord(n);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int x, int y) -> bool {
return p[x] - dist[x][0] > p[y] - dist[y][0];
});
int best = INF;
for (int i : ord) {
best = std::min(best, p[i]);
best_f[p[i] - dist[i][0]] = best;
}
best = -INF;
std::sort(ord.begin(), ord.end(), [&](int x, int y) -> bool {
return p[x] + dist[x][0] < p[y] + dist[y][0];
});
for (int i : ord) {
best = std::max(best, p[i]);
best_r[p[i] + dist[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 = std::min(best, (it->second) - d);
}
it = best_r.upper_bound(d);
if (it != best_r.begin()) {
--it;
best = std::min(best, d - (it->second));
}
return best;
}
