Là một người yêu thích kiến trúc hiện đại, nông dân John (FJ) đã xây dựng một chuồng bò mới theo dạng hình tròn hoàn hảo. Bên trong, chuồng bò hình tròn này được chia thành ~n~ phòng, đánh số ~1,2,\dots,n~ theo chiều kim đồng hồ quanh chu vi hình tròn. Mỗi phòng đều có hai cửa thông sang phòng bên cạnh cùng với một cửa hướng ra ngoài. FJ có ~n~ con bò và anh ta muốn bố trí sao cho mỗi phòng chứa đúng một con bò.

Lý tưởng nhất là khi về chuồng mỗi phòng có đúng một con bò xếp hàng đứng ở cửa hướng ra ngoài. Tuy nhiên chúng thường đi theo đàn và khi về đến chuồng, số bò xếp hàng trước cửa hướng ra ngoài của mỗi phòng là khác nhau. Cụ thể, có ~c_i~ con bò đứng xếp hàng ở cửa hướng ra ngoài của phòng ~i~. Tất nhiên ~c_i \ge 0~ với mọi ~i~ và ~\sum_{i=1}^{n}c_i=n~.

FJ sẽ cho các con bò vào chuồng theo quy tắc sau: Các con bò sẽ đi vào chuồng theo cửa mà nó đứng, sau đó đi vòng quanh các phòng trong chuồng theo chiều kim đồng hồ. Phòng trống đầu tiên mà con bò gặp sẽ là phòng nó ngủ qua đêm. Nếu một con bò di chuyển qua ~d~ phòng, nó sẽ tiêu thụ một lượng năng lượng là ~d^2~.

Yêu cầu: Hãy tính tổng năng lượng tối thiểu mà ~n~ con bò phải bỏ ra để di chuyển về phòng theo quy tắc mô tả bên trên.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(3 \le n \le 10^5)~;

• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên không âm ~c_i~.

Output

In ra một số nguyên là tổng năng lượng tối thiểu tìm được.

Sample Input 1

10
1
0
0
2
0
0
1
2
2
2

Sample Output 1

33