#include "circus.h"
#include <string.h>
const int N = 100001;
const int INF = 0x3f3f3f3f;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N], xx1[N], xx2[N], yy[N], ii[N], ii1[N], ii2[N], n;
int compare_x(int i, int j) {
return xx[i] - xx[j];
}
int compare_xpy(int i, int j) {
return (xx[i] + yy[i]) - (xx[j] + yy[j]);
}
int compare_xmy(int i, int j) {
return (xx[i] - yy[i]) - (xx[j] - yy[j]);
}
int (*compare)(int, int);
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int dd[N * 2], iq[N * 2 + 1], pq[N * 2], cnt;
int lt(int i, int j) { return dd[i] < dd[j]; }
int p2(int p) {
return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add_last(int i) {
iq[pq[i] = ++cnt] = i;
}
int pq_remove_first() {
int i = iq[1], j = iq[cnt--];
if (j != i)
pq[j] = 1, pq_dn(j);
pq[i] = 0;
return i;
}
void init(int n_, int m, int *xx_) {
n = n_;
for (int i = 0; i < n; i++)
xx[i] = xx_[i];
xx[n++] = m;
for (int i = 0; i < n; i++)
ii[i] = i;
compare = compare_x, sort(ii, 0, n);
memset(dd, 0x3f, n * 2 * sizeof *dd);
dd[n - 1 << 1 | 0] = 0, pq_add_last(n - 1 << 1 | 0);
while (cnt) {
int u, v, i, t, d;
u = pq_remove_first(), i = u >> 1, t = (u & 1);
if (t == 0) {
if (i > 0) {
v = i - 1 << 1 | 0, d = dd[u] + xx[ii[i]] - xx[ii[i - 1]];
if (dd[v] > d) {
if (dd[v] == INF)
pq_add_last(v);
dd[v] = d, pq_up(v);
}
}
} else {
if (i + 1 < n) {
v = i + 1 << 1 | 1, d = dd[u] + xx[ii[i + 1]] - xx[ii[i]];
if (dd[v] > d) {
if (dd[v] == INF)
pq_add_last(v);
dd[v] = d, pq_up(v);
}
}
}
int lower, upper, j;
lower = i - 1, upper = n;
while (upper - lower > 1) {
j = (lower + upper) / 2;
if (xx[ii[j]] - xx[ii[i]] >= dd[u])
upper = j;
else
lower = j;
}
j = upper;
if (j < n) {
v = j << 1 | 1, d = xx[ii[j]] - xx[ii[i]];
if (dd[v] > d) {
if (dd[v] == INF)
pq_add_last(v);
dd[v] = d, pq_up(v);
}
}
lower = -1, upper = i + 1;
while (upper - lower > 1) {
j = (lower + upper) / 2;
if (xx[ii[i]] - xx[ii[j]] >= dd[u])
lower = j;
else
upper = j;
}
j = lower;
if (j >= 0) {
v = j << 1 | 0, d = xx[ii[i]] - xx[ii[j]];
if (dd[v] > d) {
if (dd[v] == INF)
pq_add_last(v);
dd[v] = d, pq_up(v);
}
}
}
for (int i = 0; i < n; i++)
yy[ii[i]] = min(dd[i << 1 | 0], dd[i << 1 | 1]);
for (int i = 0; i < n; i++)
ii1[i] = i;
compare = compare_xpy, sort(ii1, 0, n);
for (int i = 0; i < n; i++)
xx1[i] = max(i == 0 ? -INF : xx1[i - 1], xx[ii1[i]]);
for (int i = 0; i < n; i++)
ii2[i] = i;
compare = compare_xmy, sort(ii2, 0, n);
for (int i = n - 1; i >= 0; i--)
xx2[i] = min(i + 1 == n ? INF : xx2[i + 1], xx[ii2[i]]);
}
int minLength(int x) {
int lower, upper, i, ans;
ans = INF;
lower = -1, upper = n;
while (upper - lower > 1) {
i = (lower + upper) / 2;
if (xx[ii1[i]] + yy[ii1[i]] <= x)
lower = i;
else
upper = i;
}
i = lower;
if (i >= 0)
ans = min(ans, x - xx1[i]);
lower = -1, upper = n;
while (upper - lower > 1) {
i = (lower + upper) / 2;
if (xx[ii2[i]] - yy[ii2[i]] >= x)
upper = i;
else
lower = i;
}
i = upper;
if (i < n)
ans = min(ans, xx2[i] - x);
return ans;
}
