cp-problems

危険な火薬庫

問題文

\(N\) 個のドアが設置された火薬庫があり，ドアには左から順に \(1,\ 2,\ \dots,\ N\) の番号がつけられています．

各ドア \(i\) には，そのドアが開いているときの危険度 \(A_i\) が定まっており，現在すべてのドアが閉まっています．

これから換気のために，ドアをいくつか開けることを考えています．

ドアをいくつか開けたときの火薬庫の危険度は以下のように定義されます．

• ドア \(L,\ L+1,\ \dots,\ R\) が開いていて，かつドア \(L-1,\ R+1\) が閉まっている / 存在しないようなドアの集合（ドア \(L,\ L+1,\ \dots,\ R\)）を \(1\) つの連結成分とし，この連結成分の危険度を \({\left(\displaystyle \sum_{L\le i\le R} A_i \right)}^2\) とする．
• 火薬庫の危険度をすべての連結成分の危険度の和とする．

各 \(k = 1,\ 2,\ …,\ N\) に対して，適切に開けるドアを \(k\) 個選んだときの火薬庫の危険度の最小値を求めてください．

制約

• \(1 \le N \le 3000\)
• \(1 \le A_i \le 100000\)
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます．

入力
\(N\) \(A_1\ A_2\ \dots \, A_N\)

出力

\(k \, (1 \le k \le N)\) 行目には，開けるドアを \(k\) 個適切に選んだときの，火薬庫の危険度の最小値を出力してください．

最後に改行してください．

解説