#include "circus.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MAX_N = 1e5 + 2;
const ll MX64 = 1e18;
int posSize;
array<ll, MAX_N> rpos, rd, ld;
vector<pll> liner, linel;
vector<ll> ri, li;
void init(int N, int M, int P[]) {
posSize = N;
for (int i = 0; i < N; i++) {
rpos[i] = P[i];
}
sort(rpos.begin(), rpos.begin() + N);
rpos[N] = M;
rd.fill(MX64), ld.fill(MX64);
using T = pair<ll, pair<ll, bool>>;
priority_queue<T, vector<T>, greater<T>> pq;
ld[N] = 0, rd[N] = 0, ld[N - 1] = rpos[N] - rpos[N - 1];
pq.push({rpos[N] - rpos[N - 1], {N - 1, false}});
while (!pq.empty()) {
auto [d, u] = pq.top();
auto [i, rs] = u;
pq.pop();
if ((rs && rd[i] != d) || (!rs && ld[i] != d)) continue;
if (rpos[i] - d >= rpos[0]) {
ll pi =
upper_bound(rpos.begin(), rpos.begin() + N + 1, rpos[i] - d) -
rpos.begin();
if (rpos[pi] > rpos[i] - d) pi--;
if (ld[pi] > rpos[i] - rpos[pi]) {
ld[pi] = rpos[i] - rpos[pi];
pq.push({ld[pi], {pi, false}});
}
}
if (rpos[i] + d < rpos[N]) {
ll ni =
lower_bound(rpos.begin(), rpos.begin() + N + 1, rpos[i] + d) -
rpos.begin();
if (rpos[ni] < rpos[i] + d) ni++;
if (rd[ni] > rpos[ni] - rpos[i]) {
rd[ni] = rpos[ni] - rpos[i];
pq.push({rd[ni], {ni, true}});
}
}
if (rs) {
if (i < N) {
ll ni = i + 1;
if (rd[ni] > d + rpos[ni] - rpos[i]) {
rd[ni] = d + rpos[ni] - rpos[i];
pq.push({rd[ni], {ni, true}});
}
}
} else {
if (i > 0) {
ll pi = i - 1;
if (ld[pi] > d + rpos[i] - rpos[pi]) {
ld[pi] = d + rpos[i] - rpos[pi];
pq.push({ld[pi], {pi, false}});
}
}
}
}
for (int i = 0; i <= N; ++i) {
ll d = min(ld[i], rd[i]);
linel.push_back({rpos[i] - d, d}), liner.push_back({rpos[i] + d, d});
}
sort(linel.begin(), linel.end()), sort(liner.begin(), liner.end());
ll rVal = liner[0].second, rPos = liner[0].first;
for (int i = 1; i < liner.size(); i++) {
ll nVal = rVal + liner[i].first - rPos;
if (liner[i].second > nVal) {
liner[i].second = nVal;
} else {
rVal = liner[i].second;
rPos = liner[i].first;
}
}
ll lVal = linel[linel.size() - 1].second,
lPos = linel[linel.size() - 1].first;
for (int i = linel.size() - 2; i >= 0; --i) {
ll nVal = lVal + lPos - linel[i].first;
if (linel[i].second > nVal) {
linel[i].second = nVal;
} else {
lVal = linel[i].second;
lPos = linel[i].first;
}
}
sort(linel.begin(), linel.end()), sort(liner.begin(), liner.end());
for (int i = 0; i < liner.size(); i++) {
ri.push_back(liner[i].first);
}
for (int i = 0; i < linel.size(); i++) {
li.push_back(linel[i].first);
}
}
int minLength(int D) {
ll ans = MX64;
auto r = upper_bound(ri.begin(), ri.end(), D) - ri.begin();
if (ri[r] > D) r--;
if (r >= 0) ans = min(ans, D - liner[r].first + liner[r].second);
auto l = lower_bound(li.begin(), li.end(), D) - li.begin();
if (li[l] < D) l++;
if (l < linel.size()) ans = min(ans, linel[l].first - D + linel[l].second);
return ans;
}
