You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

本题与 金组同名题目 在题意上一致，唯一的差别是数据范围。

题目描述

作为当代建筑的爱好者，Farmer John 建造了一个圆形新谷仓，谷仓内部 $n$ 个房间排成环形（$3 \leq n \leq 1000$），按顺时针顺序编号为 $1\ldots n$，每个房间都有通往与其相邻的左右房间的门，还有一扇门通往外面。

现在 FJ 有 $n$ 头奶牛，他的目标是让每个房间恰好有一头奶牛。然而不幸的是，现在奶牛们随意呆在某个房间里，第 $i$ 个房间里有 $c_i$ 头奶牛。保证 $\sum c_i =n$。

FJ 决定采用这样的方法来解决这个问题：让某些奶牛顺时针穿过某些房间到达指定的位置。如果一头奶牛穿过了 $d$ 扇门，他消耗的能量为 $d^2$。你需要帮 FJ 算出所有奶牛消耗的能量和最小值是多少。

输入格式

第一行一个整数 $n$，接下来 $n$ 行，第 $i$ 行一个整数 $c_i$。

输出格式

输出所有奶牛最小消耗能量和。

10
1
0
0
2
0
0
1
2
2
2

33