#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "shortcut.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
const ll inf = 1e18;
ll find_shortcut(int n, vector<int> l, vector<int> a, int c) {
reverse(l.begin(), l.end()), l.push_back(0), reverse(l.begin(), l.end()), l.push_back(0);
reverse(a.begin(), a.end()), a.push_back(-1), reverse(a.begin(), a.end());
ll prf[n + 2]{}, vals[n + 2];
prf[1] = 1;
for (int i = 2; i <= n; i++) {
prf[i] = prf[i - 1] + l[i - 1];
}
for (int i = 1; i <= n; i++) {
vals[i] = prf[i];
}
sort(vals + 1, vals + n + 1);
ll s[n + 2]{}, d[n + 2]{};
for (int i = 1; i <= n; i++) {
s[i] = prf[i] + a[i];
d[i] = prf[i] - a[i];
}
array<ll, 3> vals2[n + 1];
for (int i = 1; i <= n; i++) {
vals2[i] = {prf[i] + a[i], s[i], d[i]};
}
sort(vals2 + 1, vals2 + n + 1);
vector<int> order(n);
for (int i = 1; i <= n; i++) {
order[i - 1] = i;
}
sort(order.begin(), order.end(), [&] (int x, int y) {return prf[x] - a[x] > prf[y] - a[y];});
auto check = [&] (ll t) {
ll l1 = -inf, r1 = inf, l2 = -inf, r2 = inf;
int ptr = n;
ll mxs[2] = {-inf, -inf}, mnd[2] = {inf, inf};
for (auto i : order) {
while (ptr > 0 && vals2[ptr][0] > t + prf[i] - a[i]) {
mxs[1] = max(mxs[1], vals2[ptr][1]);
if (mxs[0] < mxs[1]) swap(mxs[0], mxs[1]);
mnd[1] = min(mnd[1], vals2[ptr][2]);
if (mnd[0] > mnd[1]) swap(mnd[0], mnd[1]);
ptr--;
}
ll sj = mxs[0], dj = mnd[0];
if (prf[i] + a[i] > t + prf[i] - a[i]) {
if (mxs[0] == s[i]) sj = mxs[1];
if (mnd[0] == d[i]) dj = mnd[1];
}
l1 = max(l1, s[i] + sj - t + c);
r1 = min(r1, d[i] + dj + t - c);
l2 = max(l2, - d[i] + sj - t + c);
r2 = min(r2, - s[i] + dj + t - c);
}
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// if (i == j) continue;
// if (prf[j] + a[j] > t + prf[i] - a[i]) {
// l1 = max(l1, s[i] + s[j] - t + c);
// r1 = min(r1, d[i] + d[j] + t - c);
// l2 = max(l2, - d[i] + s[j] - t + c);
// r2 = min(r2, - s[i] + d[j] + t - c);
// }
// }
// }
ptr = n;
ll mn = 1e18;
int lst = 0;
for (int x = 1; x <= n; x++) {
if (prf[x] > (l1 - l2) / 2) {
break;
}
lst = x;
ll st = l1 - vals[x];
while (ptr > 0 && st <= vals[ptr]) {
mn = min(mn, vals[ptr]);
ptr--;
}
ll en = min(r1 - vals[x], r2 + vals[x]);
if (mn <= en) {
return true;
}
}
ptr = n, mn = 1e18;
for (int x = n; x > lst; x--) {
ll st = l2 + vals[x];
while (ptr > 0 && st <= vals[ptr]) {
mn = min(mn, vals[ptr]);
ptr--;
}
ll en = min(r1 - vals[x], r2 + vals[x]);
if (mn <= en) {
return true;
}
}
return false;
};
ll st = 0, en = 2e15;
while (st <= en) {
ll md = (st + en) >> 1;
if (check(md)) {
en = md - 1;
} else {
st = md + 1;
}
}
return st;
}
