#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 int N = 3005;
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]{};
for (int i = 2; i <= n; i++) {
prf[i] = prf[i - 1] + l[i - 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];
}
auto check = [&] (ll t) {
ll l1 = -1e18, r1 = 1e18, l2 = -1e18, r2 = 1e18;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (i == j) continue;
if (prf[j] - prf[i] + a[i] + a[j] > t) {
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);
}
}
}
for (int x = 1; x <= n; x++) {
ll st = max(l1 - prf[x], l2 + prf[x]);
ll en = min(r1 - prf[x], r2 + prf[x]);
for (int y = 1; y <= n; y++) {
if (st <= prf[y] && prf[y] <= en) {
return true;
}
}
}
return false;
};
ll st = 0, en = 1ll << 41;
while (st <= en) {
ll md = (st + en) >> 1;
if (check(md)) {
en = md - 1;
} else {
st = md + 1;
}
}
return st;
}
