문제

현대적인 건축물에 관심이 많은 영우는 원형으로 된 새로운 강의실을 만들었다. 강의실 내부에는 $1$번부터 $n$번까지 시계 방향으로 번호가 매겨진 $n$개의 좌석이 원형으로 배치되어 있다 ($3 \le n \le 1\,000$). 각 좌석 앞에는 외부와 통하는 문이 하나씩 있으며, 각 좌석은 인접한 두 좌석과 연결되어 있다.

영우는 $n$명의 학생을 각 좌석에 정확히 한 명씩 앉히려고 한다. 하지만 학생들은 각자 임의의 문 앞에 줄을 서 있어서, 어떤 문 앞에는 여러 명의 학생이 서 있고 어떤 문 앞에는 아무도 없을 수 있다. $i$번 좌석의 문 앞에 서 있는 학생의 수를 $c_i$라고 하면, 학생 수의 총합은 $\sum c_i = n$을 만족한다.

모든 좌석에 학생을 한 명씩 배치하기 위해 영우는 다음과 같은 규칙을 정했다. 각 학생은 처음에 자신이 서 있던 문을 통해 강의실로 들어온 뒤, 빈 좌석을 찾을 때까지 시계 방향으로 이동한다. 학생이 $d$개의 좌석을 이동하며 지날 때 $d^2$만큼의 에너지를 소모한다면, 모든 학생을 좌석에 한 명씩 배치하는 데 필요한 에너지 소모량의 최솟값을 구하시오.

입력

첫째 줄에 좌석의 수 $n$이 주어진다. ($3 \le n \le 1\,000$)

이어서 $n$개의 줄에 걸쳐 $1$번 좌석부터 $n$번 좌석까지 각 문 앞에 서 있는 학생의 수 $c_1, c_2, \dots, c_n$이 한 줄에 하나씩 주어진다.

출력

모든 학생을 좌석에 한 명씩 배치하는 데 필요한 최소 에너지 소모량을 출력한다.

예제 입력 1

10
1
0
0
2
0
0
1
2
2
2

예제 출력 1

33