#include <bits/stdc++.h>
#define ent '\n'
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
typedef long long ll;
using namespace std;
const int maxn = 2e5+12;
ll pref[maxn];
int p[maxn];
int D[maxn];
int n;
long long find_shortcut(int N, vector <int> l, vector <int> d, int c){
n = N;
for(int i=1;i<n;i++){
pref[i] = pref[i-1] + l[i-1];
p[i] = i;
p[i-1] = i-1;
D[i] = d[i], D[i-1] = d[i-1];
}
sort(p, p+n, [](int i, int j){
return D[i] > D[j];
});
ll ans = 1e18;
for(int i=n-1;i>=0;i--){
for(int j=n-1;j>i;j--){
int y = p[j], x = p[i];
if(x > y) swap(x, y);
ll val = *max_element(d.begin(), d.end()), mn = 0;
ll mxl = 0, mxr = 0;
for(int i=0;i<=x;i++) {
if(i != x) mxl = max(mxl, pref[x] - pref[i] + d[i]);
val = max(val, pref[i] + d[i] + mn);
mn = max(mn, d[i] - pref[i]);
}
if(val >= ans) continue;
mn = -pref[y];
for(int i=y;i<n;i++){
if(i != y) mxr = max(mxr, pref[i] - pref[y] + d[i]);
val = max(val, pref[i] + d[i] + mn);
mn = max(mn, d[i] - pref[i]);
}
ll cur = val;
val = max(val, mxl + mxr + min(pref[y] - pref[x], (ll)c));
if(val >= ans) continue;
for(int i=x;i<=y;i++){
val = max(val, mxl + min(pref[i] - pref[x], pref[y] - pref[i] + c) + d[i]);
val = max(val, mxr + min(pref[y] - pref[i], pref[i] - pref[x] + c) + d[i]);
for(int j=i+1;j<=y;j++){
val = max(val, min(pref[j] - pref[i], pref[i] - pref[x] + pref[y] - pref[j] + c) + d[i] + d[j]);
}
if(val >= ans) break;
}
ans = min(ans, val);
}
}
return ans;
}
