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

Farmer John sở hữu \(n\) con bò và muốn đúng một con bò ở lại trong mỗi phòng của chuồng. Tuy nhiên, vì hơi bối rối, đàn bò xếp hàng lộn xộn trước các cửa, và có thể có nhiều con bò xếp hàng trước cùng một cửa. Chính xác \(c_i\) con bò xếp hàng bên ngoài cửa vào phòng \(i\), do đó \(\sum c_i=n\).

Để lùa bò sao cho mỗi phòng có một con, Farmer John muốn áp dụng cách sau: mỗi con bò đi vào qua cửa nơi nó xếp hàng ban đầu, rồi đi theo chiều kim đồng hồ qua các phòng cho đến khi đến một vị trí thích hợp. Biết rằng một con bò đi qua \(d\) cửa sẽ tiêu tốn \(d^2\) đơn vị năng lượng, hãy xác định lượng năng lượng nhỏ nhất cần thiết để phân bổ đàn bò sao cho mỗi phòng có một con.

Dữ liệu vào

Dòng đầu tiên chứa \(n\). Mỗi dòng trong \(n\) dòng còn lại lần lượt chứa \(c_1 \ldots c_n\).

Dữ liệu ra

In lượng năng lượng nhỏ nhất mà đàn bò tiêu tốn.

Ví dụ

10
1
0
0
2
0
0
1
2
2
2

33

Nguồn

USACO 2016 February Contest, Gold - Circular Barn: https://usaco.org/index.php?page=viewproblem2&cpid=621

Tác giả: Brian Dean.