#include <bits/stdc++.h>
#include "circus.h"
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 3e5 + 5;
int dp[mn], p[mn], n, m;
bool vis[mn];
vector<pii> sumOpt, difOpt;
int node (int layer, int i) { return layer * n + i; }
void dijkstra (int source) {
priority_queue<pii> pq; pq.emplace(0, source);
fill(dp, dp + 3 * n, INT_MAX), dp[source] = 0;
function<void(int,int,int)> addTransition = [&] (int from, int to, int weight) {
if (dp[from] + weight < dp[to]) {
dp[to] = dp[from] + weight;
pq.emplace(-dp[to], to);
}
};
while (pq.size()) {
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = 1;
int layer = u / n, idx = u % n;
if (layer == 0) { /// real node
// pass to suffix layer
int sfx = lower_bound(p, p + n, dp[u] + p[idx]) - p;
if (0 <= sfx && sfx < n)
addTransition(u, node(1, sfx), p[sfx] - p[idx] - dp[u]);
// pass to prefix layer
int prf = upper_bound(p, p + n, p[idx] - dp[u]) - p - 1;
if (0 <= prf && prf < n)
addTransition(u, node(2, prf), p[idx] - p[prf] - dp[u]);
}
else if (layer == 1) { /// suffix node
// pass to real layer
addTransition(u, idx, 0);
// pass to suffix layer
if (idx + 1 < n)
addTransition(u, node(1, idx + 1), p[idx + 1] - p[idx]);
}
else if (layer == 2) { /// prefix node
// pass to real layer
addTransition(u, idx, 0);
// pass to prefix layer
if (idx - 1 >= 0)
addTransition(u, node(2, idx - 1), p[idx] - p[idx - 1]);
}
}
}
void init (int N, int M, int P[]) {
/// input processing
for (int i = 0; i < N; i++) p[i] = P[i];
p[N] = M, n = N + 1, m = M;
sort(p, p + n);
/// run dijkstra
int source = lower_bound(p, p + n, M) - p;
dijkstra(node(0, source));
/// preprocessing
for (int i = 0; i < n; i++) {
sumOpt.emplace_back(p[i] + dp[i], p[i]);
difOpt.emplace_back(p[i] - dp[i], p[i]);
}
sort(all(sumOpt)), sort(all(difOpt));
for (int i = 1; i < n; i++)
sumOpt[i].second = max(sumOpt[i].second, sumOpt[i - 1].second);
for (int i = n - 2; i >= 0; i--)
difOpt[i].second = min(difOpt[i].second, difOpt[i + 1].second);
}
int minLength (int D) {
int ans = INT_MAX;
int toLeft = upper_bound(all(sumOpt), make_pair(D, INT_MAX)) - sumOpt.begin() - 1;
int toRight = lower_bound(all(difOpt), make_pair(D, 0)) - difOpt.begin();
if (0 <= toLeft && toLeft < n)
ans = min(ans, D - sumOpt[toLeft].second);
if (0 <= toRight && toRight < n)
ans = min(ans, difOpt[toRight].second - D);
return ans;
}
#ifdef LOCAL
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N = 3, M = 8;
int P[3] = {0, 3, 6};
init(N, M, P);
cout << minLength(4) << " " << minLength(5) << "\n";
return 0;
}
#endif // LOCAL
