#include "shortcut.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
using vi = vector<int>;
using ll = long long;
using ii = pair<int, int>;
ll find_shortcut(int n, vi l, vi d, int c) {
vector<ll> sl;
for(int i = 0; i < n - 1; ++i) {
sl.push_back(l[i]);
if(i) sl[i] += sl[i - 1];
}
auto dist_direct = [&](int u, int v) {
if(u > v) swap(u, v);
if(!v) return 0ll;
if(u) return sl[v - 1] - sl[ u - 1 ];
else return sl[v - 1];
};
vector<vector<ll> > DD(n, vector(n, 0ll));
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) DD[i][j] = dist_direct(i, j);
auto dist = [&](int u, int v, int st, int dr) { /// (st, dr) express line
ll re = DD[u][v];
re = min(re, DD[u][st] + DD[dr][v] + c);
// re = min(re, DD[u][dr] + DD[st][v] + c);
return re + d[u] + d[v];
};
ll reg = 1e18;
map<ii, ll> M;
auto simu = [&](int st, int dr) {
if(M.count({st, dr})) return M[{st, dr}];
ll cre = 0;
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n; ++j) {
ll val = dist(i, j, st, dr);
if(val > cre) {
cre = val;
}
}
M[{st, dr}] = cre;
return cre;
};
map<int, ll> CST;
auto cost_st = [&](int st) {
if(CST.count(st)) return CST[st];
ll re = 1e18;
int l = st + 1, r = n - 1;
while(l + 50 < r) {
int m1 = (2 * l + r) / 3, m2 = (2 * r + l) / 3;
auto c1 = simu(st, m1);
auto c2 = simu(st, m2);
re = min(re, c1);
re = min(re, c2);
if(c1 == c2) {
auto r1 = simu(st, r);
re = min(r1, re);
--r;
continue;
}
if(c1 > c2) {
l = m1;
} else r = m2;
}
for(int dr = l; dr <= r; ++dr) {
auto cre = simu(st, dr);
re = min(re, cre);
}
CST[st] = re;
return re;
};
int st = 0, dr = n - 1;
while(st + 50 < dr) {
int m1 = (2 * st + dr) / 3, m2 = (st + 2 * dr) / 3;
auto c1 = cost_st(m1);
auto c2 = cost_st(m2);
reg = min(reg, c1);
reg = min(reg, c2);
if(c1 == c2) {
auto c3 = cost_st(dr);
reg = min(reg, c3);
--dr;
continue;
} else {
if(c1 > c2) {
st = m1;
} else
dr = m2;
}
}
for(int i = st; i <= dr; ++i)
reg = min(reg, cost_st(i));
return reg;
}
