원형 헛간

현대 건축을 좋아하는 농부 존이 완벽한 원 모양으로 헛간을 새로 지었다. 헛간 안에는 방 $n$개가 고리처럼 이어져 있고, 헛간 둘레를 따라 시계 방향으로 $1$번부터 $n$번까지 번호가 붙어 있다 ($3 \le n \le 100000$). 각 방에는 양옆 방으로 통하는 문 두 개와 헛간 바깥으로 통하는 문 하나가 있다.

존은 소 $n$마리를 키우고, 방마다 소가 정확히 한 마리씩 들어가기를 바란다. 그런데 소들은 바깥문 아무 곳에나 줄을 서고, 한 문 앞에 여러 마리가 서기도 한다. $i$번 방의 바깥문 앞에는 소가 정확히 $c_i$마리 서 있고, $\sum c_i = n$이다.

존은 다음 방식으로 소를 몬다. 소는 자기가 줄을 선 문으로 들어간 뒤, 자신이 들어갈 방에 닿을 때까지 시계 방향으로 방을 지나 걷는다. 문을 $d$개 지나 걸은 소는 에너지를 $d^2$만큼 쓴다. 방마다 소가 한 마리씩 들어가도록 배치할 때, 소들이 쓰는 에너지의 합이 최소가 되게 하려고 한다. 그 최솟값을 구하여라.

첫째 줄에 $n$이 주어진다. 이어지는 $n$개 줄에 $c_1$부터 $c_n$까지 한 줄에 하나씩 순서대로 주어진다.

소들이 쓰는 에너지의 합의 최솟값을 출력한다.