#include #include #include using namespace std; using ll = long long; const ll INF = 1e18; struct ConvexHullTrick { using F = pair<__int128, __int128>; deque deq; #define a first #define b second #define lines deq.size() bool invalid_f1(F f0, F f1, F f2) { return (f1.a - f0.a) * (f2.b - f1.b) >= (f1.b - f0.b) * (f2.a - f1.a); } ll f(F f0, ll x) { return f0.a * x + f0.b; } void add(F f0) { while (lines >= 2 && invalid_f1(deq[lines - 2], deq[lines - 1], f0)) { deq.pop_back(); } deq.push_back(f0); } ll min(ll x) { while (lines >= 2 && f(deq[0], x) >= f(deq[1], x)) { deq.pop_front(); } return f(deq[0], x); } }; int main() { int N; cin >> N; ll S[N + 1], DP[N + 2][N + 1]; S[0] = 0; for (int i = 0; i < N; i++) cin >> S[i + 1], S[i + 1] += S[i]; for (int i = 0; i < N + 2; i++) { for (int j = 0; j < N + 1; j++) DP[i][j] = INF; } for (int i = 0; i < N + 2; i++) DP[i][0] = 0; for (int i = 0; i < N + 2; i++) { ConvexHullTrick CHT; for (int j = 0; j < N + 1; j++) { if (i + j + 1 > N + 1) break; ll A = -2 * S[i + j], B = S[i + j] * S[i + j] + DP[i + j][j]; ll X = S[i + j], Y = S[i + j] * S[i + j]; CHT.add(make_pair(A, B)); DP[i + j + 1][j] = min(DP[i + j + 1][j], CHT.min(X) + Y); } } for (int i = 0; i < N; i++) { cout << min(DP[N][i + 1], DP[N + 1][i + 1]) << endl; } }