#include "circus.h"
#define ll long long
#define pii pair<ll, ll>
#include <bits/stdc++.h>
using namespace std;
ll gN, gM;
const ll MAX_N = 1000010, MAX_Q = 1000010;
const ll INF = 1e15;
struct persistent_array
{
private:
vector<vector<pair<ll, pii>>> arr;
ll n;
vector<ll> idxs;
public:
persistent_array() {}
void build(ll _n)
{
n = _n;
arr.resize(n);
idxs.resize(n, n);
}
pii get_item(ll idx, ll t)
{
ll l = 0, r = arr[idx].size() - 1;
ll lb = -1;
while (l <= r)
{
ll m = l + (r - l) / 2;
if (arr[idx][m].first >= t)
{
lb = m;
l = m + 1;
}
else
r = m - 1;
}
return arr[idx][lb].second;
}
void update_item(ll idx, ll t, pii val)
{
arr[idx].push_back({t, val});
idxs[t] = idx;
}
ll get_idx(ll t)
{
return idxs[t];
}
};
ll dist[MAX_N][2], iarr[MAX_N];
ll dp[MAX_N];
persistent_array back_arr, front_arr;
void init(int N, int M, int P[])
{
gN = N;
gM = M;
for (ll i = 0; i < N; i++)
{
iarr[i] = P[i];
dist[i][0] = dist[i][1] = INF;
}
iarr[N] = M;
dist[N][0] = dist[N][1] = INF;
// dijkstra, 0 = left; 1 = right
dist[N][0] = dist[N][1] = 0;
priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> q;
q.push({0, {N, 0}});
while (!q.empty())
{
ll w = q.top().first;
auto [v, t] = q.top().second;
q.pop();
if (dist[v][t] < w)
continue;
// go left
ll lb = upper_bound(iarr, iarr + N + 1, iarr[v] - w) - iarr;
--lb;
if (lb == v)
--lb;
if (lb >= 0 && dist[lb][0] > iarr[v] - iarr[lb])
{
dist[lb][0] = iarr[v] - iarr[lb];
q.push({dist[lb][0], {lb, 0}});
}
// go right
ll rb = lower_bound(iarr, iarr + N + 1, iarr[v] + w) - iarr;
if (rb == v)
rb++;
if (rb <= N && dist[rb][1] > iarr[rb] - iarr[v])
{
dist[rb][1] = iarr[rb] - iarr[v];
q.push({dist[rb][1], {rb, 1}});
}
// continue to the same direction
if (t == 0 && v - 1 >= 0 && dist[v - 1][0] > w + iarr[v] - iarr[v - 1])
{
dist[v - 1][0] = iarr[v] - iarr[v - 1];
q.push({dist[v - 1][0], {v - 1, 0}});
}
if (t == 1 && v + 1 <= N && dist[v + 1][1] > w + iarr[v + 1] - iarr[v])
{
dist[v + 1][1] = w + iarr[v + 1] - iarr[v];
q.push({dist[v + 1][1], {v + 1, 1}});
}
}
for (ll i = 0; i <= N; i++)
dp[i] = min(dist[i][0], dist[i][1]);
back_arr.build(N + 1);
front_arr.build(N + 1);
back_arr.update_item(N, N, {M, M});
ll idx = N;
for (ll i = N - 1; i >= 0; i--)
{
while (back_arr.get_item(idx, i).first <= P[i] - dp[i])
idx++;
--idx;
back_arr.update_item(idx, i, {P[i] - dp[i], P[i]});
}
front_arr.update_item(N, N, {P[0] - dp[0], 0});
idx = N;
for (ll i = 1, j = N - 1; i <= N; i++, j--)
{
while (idx <= N && front_arr.get_item(idx, j).first >= P[i] + dp[i])
idx++;
--idx;
front_arr.update_item(idx, j, {P[i] + dp[i], P[i]});
}
}
int minLength(int D)
{
ll l = 0, r = gN;
ll lb = gN;
while (l <= r)
{
ll m = l + (r - l) / 2;
if (iarr[m] >= D)
{
lb = m;
r = m - 1;
}
else
l = m + 1;
}
ll i = lb;
ll idx = back_arr.get_idx(i);
l = idx;
r = gN;
lb = gM;
while (l <= r)
{
ll m = l + (r - l) / 2;
pii item = back_arr.get_item(m, i);
if (D <= item.first)
{
lb = item.second;
r = m - 1;
}
else
l = m + 1;
}
ll res = lb - D;
l = 0;
r = gN;
lb = -INF;
while (l <= r)
{
ll m = l + (r - l) / 2;
if (iarr[m] <= D)
{
lb = m;
l = m + 1;
}
else
r = m - 1;
}
if (lb == -INF)
return res;
i = lb;
idx = front_arr.get_idx(gN - i);
l = idx;
r = gN;
lb = gM;
while (l <= r)
{
ll m = l + (r - l) / 2;
pii item = front_arr.get_item(m, gN - i);
if (D >= item.first)
{
lb = item.second;
r = m - 1;
}
else
l = m + 1;
}
res = min(res, D - lb);
return res;
}
