#include "circus.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> mnstkl,mnstkr;
typedef unsigned int uint;
const int INF = 1e9;
struct ST {
int sz;
vector<pii> mn, mn_offset;
vector<int> lz;
void pull(int t) {
mn[t] = min(mn[t*2+1], mn[t*2+2]);
mn_offset[t] = min(mn_offset[t*2+1], mn_offset[t*2+2]);
}
void push(int t) {
lz[t*2+1] = min(lz[t*2+1], lz[t]);
lz[t*2+2] = min(lz[t*2+2], lz[t]);
mn[t*2+1] = min(mn[t*2+1], {mn_offset[t*2+1].first + lz[t], mn_offset[t*2+1].second});
mn[t*2+2] = min(mn[t*2+2], {mn_offset[t*2+2].first + lz[t], mn_offset[t*2+2].second});
lz[t] = INF;
}
int _qry(int t, int l, int r, int x) {
if (r - l == 1) return mn[t].first;
else {
int m = l+r>>1;
push(t);
if (x < m) return _qry(t*2+1, l, m, x);
else return _qry(t*2+2, m, r, x);
}
}
int qry(int x) { return _qry(0,0,sz,x); }
void _upd(int t, int l, int r, int x, int v) {
if (x <= l) {
mn[t] = min(mn[t], {mn_offset[t].first + v, mn_offset[t].second});
lz[t] = min(lz[t], v);
} else {
push(t);
int m = l+r>>1;
if (x < m) _upd(t*2+1, l, m, x, v);
_upd(t*2+2, m, r, x, v);
pull(t);
}
}
void upd(int x, int v) { if (x < sz) _upd(0, 0, sz, x, v); }
void _set_offset(int t, int l, int r, int x, int v) {
if (r - l == 1) {
mn_offset[t] = {v, l};
mn[t] = {v + INF, l};
} else {
int m = l+r>>1;
push(t);
if (x < m) _set_offset(t*2+1, l, m, x, v);
else _set_offset(t*2+2, m, r, x, v);
pull(t);
}
}
void set_offset(int x, int v) { _set_offset(0, 0, sz, x, v); }
void init(int N) {
sz = N;
mn.resize(4*N, {INF, INF});
mn_offset.resize(4*N, {INF, INF});
lz.resize(4*N, INF);
}
} A, B;
void init(int N, int M, int _P[]){
vector<int> P(_P, _P+N), bst(N+1);
P.push_back(M);
sort(P.begin(), P.end());
A.init(N+1);
B.init(N+1);
for (int i = 0; i < N+1; ++i) {
A.set_offset(i, P[i]);
B.set_offset(N-i, M-P[i]);
}
A.upd(N, -M);
for (int i = 0; i < N+1; ++i) {
pii mn = A.mn[0];
if (B.mn[0] < mn) {
mn = {B.mn[0].first, N - B.mn[0].second};
}
int x = mn.first + P[mn.second];
A.upd(lower_bound(P.begin(), P.end(), x) - P.begin(), -P[mn.second]);
lower_bound(P.rbegin(), P.rend(), x, greater<int>()) - P.rbegin();
x = P[mn.second] - mn.first;
B.upd(lower_bound(P.rbegin(), P.rend(), x, greater<int>()) - P.rbegin(), P[mn.second]-M);
bst[mn.second] = min(A.qry(mn.second), B.qry(N-mn.second));
A.set_offset(mn.second, INF);
B.set_offset(N-mn.second, INF);
}
priority_queue<pii> pqr;
for (int i = 0; i < N+1; ++i) pqr.emplace(P[i] - bst[i], P[i]);
mnstkr.push_back(pqr.top());
pqr.pop();
while (pqr.size()) {
pii u = pqr.top(); pqr.pop();
if (u.second < mnstkr.back().second) mnstkr.push_back(u);
}
priority_queue<pii, vector<pii>, greater<pii>> pql;
for (int i = 0; i < N+1; ++i) pql.emplace(P[i] + bst[i], P[i]);
mnstkl.push_back(pql.top());
pql.pop();
while (pql.size()) {
pii u = pql.top(); pql.pop();
if (u.second > mnstkl.back().second) mnstkl.push_back(u);
}
}
int minLength(int D) {
int ans = INF;
auto l = lower_bound(mnstkl.begin(), mnstkl.end(), make_pair(D,INF));
if (l != mnstkl.begin()) {
l--;
ans = min(ans, D - l->second);
}
auto r = lower_bound(mnstkr.rbegin(), mnstkr.rend(), make_pair(D,0));
ans = min(ans, r->second - D);
return ans;
}
