[USACO16FEB] Circular Barn G

题目背景

*本题与 [银组同名题目](/problem/P3137) 在题意上一致,唯一的差别是数据范围。*

题目描述

作为当代建筑的爱好者,Farmer John 建造了一个圆形新谷仓,谷仓内部 $n$ 个房间排成环形($3 \leq n \leq 10^5$),按顺时针顺序编号为 $1\ldots n$,每个房间都有通往与其相邻的左右房间的门,还有一扇门通往外面。 现在 FJ 有 $n$ 头奶牛,他的目标是让每个房间恰好有一头奶牛。然而不幸的是,现在奶牛们随意呆在某个房间里,第 $i$ 个房间里有 $c_i$ 头奶牛。保证 $\sum c_i =n$。 FJ 决定采用这样的方法来解决这个问题:让某些奶牛**顺时针**穿过某些房间到达指定的位置。如果一头奶牛穿过了 $d$ 扇门,他消耗的能量为 $d^2$。你需要帮 FJ 算出所有奶牛消耗的能量和最小值是多少。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

10
1
0
0
2
0
0
1
2
2
2

输出样例 #1

33