#include <iostream>
#include <array>
#include <queue>
#include <algorithm>
#include <limits>
#include <map>
#include <vector>
#include <set>
using ll = long long;
const int MAX_N = 1000*100+2;
std::array<ll, MAX_N> ropesPos;
std::array<ll, MAX_N> rDists, lDists;
std::vector<std::pair<ll, ll>> rLines, lLines;
std::vector<ll> rLinesIdx, lLinesIdx;
void init(int N, int M, int P[]) {
for (int i = 0; i < N; ++i)
ropesPos[i] = P[i];
std::sort(ropesPos.begin(), ropesPos.begin() + N);
// ropesPos = {0, 3, 6, 6, 6, 6, 8};
// std::cout << "test = " << std::lower_bound(ropesPos.begin(), ropesPos.begin() + 7, 3) - ropesPos.begin() << std::endl;
ropesPos[N] = M;
rDists.fill(std::numeric_limits<ll>::max());
lDists.fill(std::numeric_limits<ll>::max());
using T = std::pair<ll, std::pair<ll, bool>>; // true: right-side
std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
lDists[N] = 0;
rDists[N] = 0;
lDists[N - 1] = ropesPos[N] - ropesPos[N - 1];
pq.push({ropesPos[N] - ropesPos[N - 1], {N - 1, false}});
while (!pq.empty()) {
auto [dist, node] = pq.top();
auto [idx, rightSide] = node;
pq.pop();
if ((rightSide && rDists[idx] != dist) || (!rightSide && lDists[idx] != dist)) {
continue;
}
if (ropesPos[idx] - dist >= ropesPos[0]) {
ll pidx = std::upper_bound(ropesPos.begin(), ropesPos.begin() + N + 1, ropesPos[idx] - dist) - ropesPos.begin();
if (ropesPos[pidx] > ropesPos[idx] - dist) {
pidx--;
}
if (lDists[pidx] > ropesPos[idx] - ropesPos[pidx]) {
lDists[pidx] = ropesPos[idx] - ropesPos[pidx];
pq.push({lDists[pidx], {pidx, false}});
}
}
if (ropesPos[idx] + dist < ropesPos[N]) {
ll nidx = std::lower_bound(ropesPos.begin(), ropesPos.begin() + N + 1, ropesPos[idx] + dist) - ropesPos.begin();
if (ropesPos[nidx] < ropesPos[idx] + dist) {
nidx++;
}
if (rDists[nidx] > ropesPos[nidx] - ropesPos[idx]) {
rDists[nidx] = ropesPos[nidx] - ropesPos[idx];
pq.push({rDists[nidx], {nidx, true}});
}
}
if (rightSide) {
if (idx < N) {
ll nidx = idx + 1;
if (rDists[nidx] > dist + ropesPos[nidx] - ropesPos[idx]) {
rDists[nidx] = dist + ropesPos[nidx] - ropesPos[idx];
pq.push({rDists[nidx], {nidx, true}});
}
}
} else {
if (idx > 0) {
ll pidx = idx - 1;
if (lDists[pidx] > dist + ropesPos[idx] - ropesPos[pidx]) {
lDists[pidx] = dist + ropesPos[idx] - ropesPos[pidx];
pq.push({lDists[pidx], {pidx, false}});
}
}
}
}
// std::cout << "shortest path = " << std::endl;
for (int i = 0; i <= N; ++i) {
ll d = std::min(lDists[i], rDists[i]);
// std::cout << ropesPos[i] << " " << d << std::endl;
lLines.push_back({ropesPos[i] - d, d});
rLines.push_back({ropesPos[i] + d, d});
}
std::sort(lLines.begin(), lLines.end());
std::sort(rLines.begin(), rLines.end());
for (int i = 0; i < rLines.size(); ++i) {
rLinesIdx.push_back(rLines[i].first);
}
for (int i = 0; i < lLines.size(); ++i) {
lLinesIdx.push_back(lLines[i].first);
}
ll rVal = rLines[0].second;
ll rPos = rLines[0].first;
for (int i = 1; i < rLines.size(); ++i) {
ll nVal = rVal + rLines[i].first - rPos;
if (rLines[i].second > nVal) {
rLines[i].second = nVal;
} else {
rVal = rLines[i].second;
rPos = rLines[i].first;
}
}
ll lVal = lLines[lLines.size() - 1].second;
ll lPos = lLines[lLines.size() - 1].first;
for (int i = lLines.size() - 2; i >= 0; --i) {
ll nVal = lVal + lPos - lLines[i].first;
if (lLines[i].second > nVal) {
lLines[i].second = nVal;
} else {
lVal = lLines[i].second;
lPos = lLines[i].first;
}
}
// std::cout << "right lines = " << std::endl;
// for (auto rl : rLines) {
// std::cout << rl.first << " " << rl.second << std::endl;
// }
// std::cout << "left lines = " << std::endl;
// for (auto ll : lLines) {
// std::cout << ll.first << " " << ll.second << std::endl;
// }
}
int minLength(int D) {
ll ans = std::numeric_limits<ll>::max();
auto rIdx = std::lower_bound(rLinesIdx.begin(), rLinesIdx.end(), D) - rLinesIdx.begin();
if (rLinesIdx[rIdx] > D) {
rIdx--;
}
// std::cout << "rIdx = " << rIdx << std::endl;
if (rIdx >= 0)
ans = std::min(ans, D - rLines[rIdx].first + rLines[rIdx].second);
auto lIdx = std::upper_bound(lLinesIdx.begin(), lLinesIdx.end(), D) - lLinesIdx.begin();
lIdx--;
if (lLinesIdx[lIdx] < D) {
lIdx++;
}
// std::cout << "lIdx = " << lIdx << std::endl;
if (lIdx < lLines.size())
ans = std::min(ans, lLines[lIdx].first - D + lLines[lIdx].second);
return ans;
}
