// need #include #include // data structure #include #include #include #include #include #include #include #include #include //#include #include #include #include #include // etc #include #include #include #include #include #include #include #include // input #define INIT std::ios::sync_with_stdio(false);std::cin.tie(0); #define VAR(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__); template void MACRO_VAR_Scan(T& t) { std::cin >> t; } templatevoid MACRO_VAR_Scan(First& first, Rest& ...rest) { std::cin >> first; MACRO_VAR_Scan(rest...); } #define VEC_ROW(type, n, ...)std::vector __VA_ARGS__;MACRO_VEC_ROW_Init(n, __VA_ARGS__); for(int w_=0; w_ void MACRO_VEC_ROW_Init(int n, T& t) { t.resize(n); } templatevoid MACRO_VEC_ROW_Init(int n, First& first, Rest& ...rest) { first.resize(n); MACRO_VEC_ROW_Init(n, rest...); } template void MACRO_VEC_ROW_Scan(int p, T& t) { std::cin >> t[p]; } templatevoid MACRO_VEC_ROW_Scan(int p, First& first, Rest& ...rest) { std::cin >> first[p]; MACRO_VEC_ROW_Scan(p, rest...); } #define VEC(type, c, n) std::vector c(n);for(auto& i:c)std::cin>>i; #define MAT(type, c, m, n) std::vector> c(m, std::vector(n));for(auto& R:c)for(auto& w:R)std::cin>>w; // output templatevoid MACRO_OUT(const T t) { std::cout << t; } templatevoid MACRO_OUT(const First first, const Rest...rest) { std::cout << first << " "; MACRO_OUT(rest...); } #define OUT(...) MACRO_OUT(__VA_ARGS__); #define FOUT(n, dist) std::cout<=(a);--w) #define REP(w, n) for(int w=0;w=0;--w) #define IN(a, x, b) (a<=x && x inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; } template inline T CHMIN(T& a, const T b) { return a = (a > b) ? b : a; } // test template using V = std::vector; template using VV = V>; template std::ostream& operator<<(std::ostream& os, std::pair p) { os << "(" << p.first << ", " << p.second << ")"; return os; } // type/const #define int ll using ll = long long; using ull = unsigned long long; using ld = long double; using PAIR = std::pair; using PAIRLL = std::pair; constexpr int INFINT = (1 << 30) - 1; // 1.07x10^ 9 constexpr int INFINT_LIM = (1LL << 31) - 1; // 2.15x10^ 9 constexpr ll INFLL = 1LL << 60; // 1.15x10^18 constexpr ll INFLL_LIM = (1LL << 62) - 1 + (1LL << 62); // 9.22x10^18 constexpr double EPS = 1e-10; constexpr int MOD = 1000000007; constexpr double PI = 3.141592653589793238462643383279; template void FILL(T(&a)[N], const T & val) { for (auto& x : a) x = val; } template void FILL(ARY(&a)[N][M], const T & val) { for (auto& b : a) FILL(b, val); } template void FILL(std::vector & a, const T & val) { for (auto& x : a) x = val; } template void FILL(std::vector> & a, const T & val) { for (auto& b : a) FILL(b, val); } // ------------>8------------------------------------->8------------ constexpr int B = 450; constexpr int N = 200005; constexpr int NB = N / B + 1; struct SEG { signed min[N]; }; SEG seg[NB]; signed main() { INIT; VAR(int, n); VEC(int, a, n); V c(n + 1, 0); REP(i, n) c[i + 1] = c[i] + a[i]; V v(n + 1, 0); REP(i, n + 1) v[i] = i * i - c[i]; REP(si, NB) { REP(i, N) seg[si].min[i] = INFINT; } REP(si, NB) { int l = si * B, r = (si + 1) * B; CHMIN(r, n); if (l >= r) break; RFOR(i, l, r) { int ma = 0; FOR(j, l, i) { if (v[j] >= v[i]) continue; int k = (v[i] - v[j]) / (2 * (i - j)) - 1; while (v[j] < v[i] - 2 * (i - j) * k) ++k; CHMAX(ma, k); } FOR(x, ma, N) { if (seg[si].min[x] < INFINT) break; seg[si].min[x] = i; } } } V ans(n); V mi(NB, INFLL); // -1 : 更新不要, -2 : 全部調べる, k>=0 : kで更新 std::map map; RREP(i, n) { V info(NB, -1); auto get = [&](int x) { auto it = map.lower_bound(x); int a, b; std::tie(a, b) = it->second; return a * x + b; }; int r = i + 1; int updIdx = -1; if (r == n) { map[n] = PAIR(-2 * r, r * r + c[r]); REP(j, NB) info[j] = n; } else { int a = -2 * r, b = r * r + c[r]; if (get(n) >= a * n + b) { map.clear(); map[n] = PAIR(a, b); REP(j, NB) info[j] = r; } else if (get(0) < a * 0 + b) { // info[x] = -1 } else { while (!map.empty()) { auto it = map.begin(); int ta, tb; std::tie(ta, tb) = it->second; int tx = it->first; if (ta * tx + tb >= a * tx + b) { map.erase(it); continue; } else { int y = -(tb - b) / (ta - a) - 2; while ((ta * y + tb) - (a * y + b) > 0) ++y; int sy = y / B; REP(j, sy) info[j] = r; info[sy] = -2; break; } } } } info[i / B] = -2; int res = INFLL; REP(si, NB) { int l = si * B, r = (si + 1) * B; CHMIN(r, i + 1); if (l >= r) break; if (info[si] == -1) { CHMIN(res, mi[si]); } else if (info[si] == -2) { int smi = INFLL; FOR(j, l, r) { CHMIN(smi, get(j) + v[j]); } CHMIN(res, smi); mi[si] = smi; } else { int tx = seg[si].min[info[si]]; mi[si] = get(tx) + v[tx]; CHMIN(res, mi[si]); } } ans[i] = res; } REP(i, n) { OUT(ans[i])BR; } return 0; }