원형 방

수진은 원형의 창고를 지었습니다. 내부는 완벽한 원형을 이루며, 창고 주변에는 $n$개의 방이 시계 방향으로 번호가 매겨져 있습니다 ($3 \leq n \leq 1000$). 각 방은 인접한 두 개의 방과 연결된 문을 가지고 있으며, 또한 창고의 바깥쪽으로 향하는 문도 있습니다.

수진은 $n$마리의 고양이를 가지고 있으며, 각 방에 고양이 한 마리씩이 있기를 원합니다. 그러나 고양이들은 아무곳이나 문 앞에 줄을 서 있습니다. 정확히 $c_i$ 마리의 고양이가 방 $i$의 문 앞에 있습니다. 따라서 $\sum c_i = n$입니다.

고양이들을 관리해서 각 방에 고양이 한 마리씩 들어가게 하려면 수진이는 다음과 같은 방법을 사용하려고 합니다: 각 고양이는 처음 줄을 선 문에서 들어가서 시계 방향으로 움직이며 적절한 목적지에 도착합니다. $d$개의 문을 지나가는 고양이는 $d^2$의 에너지를 소비하게 됩니다. 고양이들이 소비하는 에너지의 최소량을 구해주세요.

첫 번째 입력 줄에는 $n$이 있습니다. 나머지 $n$ 줄에는 $c_1 \ldots c_n$이 있습니다.

고양이들이 소비하는 최소 에너지 양을 적어주세요.