#include <bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define imx INT_MAX
#define imn INT_MIN
#define lmx LLONG_MAX
#define lmn LLONG_MIN
#define ld long double
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_llset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
int n, m;
vector<int> st, lazy;
void pd(int id, int l, int mid, int r) {
st[lid] = min(st[lid], lazy[id]);
st[rid] = min(st[rid], lazy[id]);
lazy[lid] = min(lazy[lid], lazy[id]);
lazy[rid] = min(lazy[rid], lazy[id]);
lazy[id] = m;
}
int query(int id, int l, int r, int pos) {
if (l == r) return st[id];
int mid = (l + r) / 2;
pd(id, l, mid, r);
if (pos <= mid) return query(lid, l, mid, pos);
return query(rid, mid + 1, r, pos);
}
void upd(int id, int l, int r, int ur, int val) {
if (ur < l) return;
if (r <= ur) {
st[id] = min(st[id], val);
lazy[id] = min(lazy[id], val);
return;
}
int mid = (l + r) / 2;
pd(id, l, mid, r);
upd(lid, l, mid, ur, val);
upd(rid, mid + 1, r, ur, val);
st[id] = min(st[lid], st[rid]);
}
vector<int> thres, pos;
void init(int N, int M, int p[]) {
n = N;
m = M;
st.resize(n * 4, m);
lazy.resize(n * 4, m);
sort(p, p + n);
pos.resize(n);
int i, cur;
for (i = 0; i < n; i++) pos[i] = p[i];
thres.resize(n);
upd(0, 0, n - 1, n, m);
for (i = n - 1; i >= 0; i--) {
cur = query(0, 0, n - 1, i);
thres[i] = cur - pos[i];
upd(0, 0, n - 1, upper_bound(pos.begin(), pos.end(), pos[i] - thres[i]) - pos.begin() - 1, pos[i]);
thres[i] = pos[i] - thres[i];
}
}
int minLength(int d) {
int tmp = lower_bound(thres.begin(), thres.end(), d) - thres.begin();
if (tmp == n) return m - d;
return pos[tmp] - d;
}
