モノグサボードゲーム店では、$N$個のボードゲームが一列に並べられています。左から$i$番目に置かれたボードゲームを商品$i$と呼び、単価は$A_i$円です。各商品の在庫はひとつだけであり、一度売れると売り切れます。商品は、次の手順で購入します。

• $1 \le L \le R \le N$となるような整数L, Rを選ぶ。ただし商品$L$, 商品$L + 1$, $\ldots$, 商品$R$の中に売り切れているものがあってはならない。
• 「商品$L$, 商品$L + 1$, $\ldots$, 商品$R$の単価の合計」から「商品$L$, 商品$L + 1$, $\ldots$, 商品$R$のうち最も単価が高いものの単価の半額」を引いた金額を支払う
• 手数料として、$(R - L) ^ 2$円を追加で支払う

$k = 1, 2, \ldots, N$について、手順を$k$回行ってすべての商品を買うときにかかる最小の金額を求めてください。形式的に述べると、区間$[1, N]$を小さい方から順に$[1, p_1], [p_1 + 1, p_2], \ldots, [p_{k - 1} + 1, N]$（ただし$k = 1$のときは$[1, N]$）と分割したときのそれぞれの区間$[l, r]$に対する$\sum_{i = l}^r A_i - \max_{l \le i \le r} A_i / 2 + (r - l) ^ 2$の総和の最小値を各$k$について求めてください。

(2025-08-08 18:35 修正) 「形式的に述べると」のところで、最大値を 2 で割りました。

• $1 \le N \le 5000$
• $2 \le A_i \le 10^9$
• $A_i$は偶数

$N$行にわたって答えを出力してください。末尾に改行を加えてください。