#include "shortcut_c.h"
#define N 1000000
#define INF 0x3f3f3f3f3f3f3f3f
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
long long *aa;
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)
if (aa[ii[j]] == aa[i_])
j++;
else if (aa[ii[j]] < aa[i_]) {
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;
}
}
long long find_shortcut(int n, int *xx_, int *dd, int c) {
static long long xx[N], yy[N], yy_[N], zz[N];
static int kk[N], ll[N];
int h1, h2, i, i_, j, j1, j2, k, lz, d1, d2, can;
long long x, y, y_, y1, z, z1, z2, z_, p, q, r, s, lower, upper, d;
for (i = 1; i < n; i++)
xx[i] = xx[i - 1] + xx_[i - 1];
d1 = d2 = -1, i_ = -1;
for (i = 0; i < n; i++) {
d = dd[i], x = xx[i], yy[i] = d - x, zz[i] = d + x;
if (d1 < d)
d2 = d1, d1 = d, i_ = i;
else if (d2 < d)
d2 = d;
kk[i] = ll[i] = i;
}
aa = yy, sort(kk, 0, n);
aa = zz, sort(ll, 0, n);
for (i = n - 1; i >= 0; i--)
yy_[i] = max(i + 1 == n ? -INF : yy_[i + 1], ll[i] == i_ ? -INF : yy[ll[i]]);
y_ = yy[i_], z_ = zz[i_], z1 = zz[ll[n - 1]], z2 = zz[ll[n - 2]], lz = ll[n - 1];
lower = d1 + d2 - 1, upper = xx[n - 1] + d1 + d2;
while (upper - lower > 1) {
d = (lower + upper) / 2;
p = q = r = s = INF;
r = kk[n - 1] != ll[n - 1] ? yy[kk[n - 1]] + zz[ll[n - 1]] : max(yy[kk[n - 1]] + zz[ll[n - 2]], yy[kk[n - 2]] + zz[ll[n - 1]]);
r = r <= d ? INF : -r;
for (h1 = 0, h2 = n - 1; h1 < n; h1++) {
k = kk[h1], y = yy[k], z = zz[k];
while (h2 >= 0 && y + zz[ll[h2]] > d)
h2--;
if (h2 + 1 == n)
continue;
if (k != lz)
p = min(p, -(z + z1));
else if (h2 + 2 < n)
p = min(p, -(z + z2));
if (k != i_ && y + z_ > d)
q = min(q, -(z + y_)), s = min(s, -(y + y_));
if ((y1 = yy_[h2 + 1]) != -INF)
q = min(q, -(z + y1)), s = min(s, -(y + y1));
}
if (p != INF)
p += d - c;
if (q != INF)
q += d - c;
if (r != INF)
r += d - c;
if (s != INF)
s += d - c;
can = 0;
for (i = 0, j1 = -1, j2 = n - 1; i < n; i++) {
x = xx[i];
while (j1 + 1 < n && - x + xx[j1 + 1] <= q)
j1++;
while (j2 >= 0 && + x + xx[j2] > s)
j2--;
j = min(j1, j2);
if (i < j && - x - xx[j] <= p && + x - xx[j] <= r) {
can = 1;
break;
}
}
if (can)
upper = d;
else
lower = d;
}
return upper;
}
