現代建築好きの Farmer John は完全な円形の新しい納屋を建てました。内部は周囲に環状に並ぶ $n$ 部屋からなり、時計回りに $1 \ldots n$ と番号が付いています（$3 \leq n \leq 100,000$）。各部屋には両隣への扉と、外へ通じる扉があります。

$n$ 頭の牛を各部屋にちょうど一頭ずつ入れたいのですが、牛は混乱して勝手な扉に並び、同じ扉に複数並ぶこともあります。部屋 $i$ の外扉に $c_i$ 頭が並び、$\sum c_i = n$ です。

各牛は最初に並んだ扉から入り、目的地まで時計回りに部屋を進みます。$d$ 枚の扉を通ると $d^2$ のエネルギーを使います。各部屋に一頭ずつ配置するための最小総エネルギーを求めてください。

入力

最初の行は $n$ です。続く $n$ 行には $c_1 \ldots c_n$ が順に一つずつ与えられます。

出力

牛が使う総エネルギーの最小値を出力してください。

入出力例

入力 1

10
1
0
0
2
0
0
1
2
2
2

出力 1

33

問題作成：Brian Dean