Là người thích kiến trúc hiện đại, Farmer John xây chuồng mới hình tròn hoàn hảo. Bên trong là vòng $n$ phòng, đánh số theo chiều kim đồng hồ $1 \ldots n$ quanh chu vi ($3 \leq n \leq 100,000$). Mỗi phòng có cửa sang hai phòng kề và một cửa ra ngoài.

Ông có $n$ cô bò và muốn đúng một cô ở mỗi phòng. Nhưng bò hơi bối rối, xếp hàng ở cửa tùy ý, có thể nhiều cô ở cùng cửa. Có đúng $c_i$ cô ngoài cửa phòng $i$, nên $\sum c_i = n$.

Mỗi cô vào bằng cửa nơi ban đầu xếp hàng rồi đi theo chiều kim đồng hồ qua các phòng đến nơi phù hợp. Đi qua $d$ cửa tiêu tốn $d^2$ năng lượng. Tìm tổng năng lượng ít nhất để phân bố đúng một cô ở mỗi phòng.

Dữ liệu vào

Dòng đầu chứa $n$. $n$ dòng tiếp theo chứa $c_1 \ldots c_n$ theo thứ tự, mỗi dòng một giá trị.

Dữ liệu ra

In tổng năng lượng ít nhất bò tiêu thụ.

Ví dụ

Dữ liệu vào 1

10
1
0
0
2
0
0
1
2
2
2

Dữ liệu ra 1

33

Tác giả: Brian Dean