원형 축사 (실버)

면접 대비

시간 제한2초메모리 제한512 MB

요약

원형 외양간 문 앞에 선 소를 시계 방향으로 이동시켜 각 방에 한 마리씩 채울 때 이동 거리의 제곱합이 최소가 되도록 합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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

농부 존은 소 $n$ 마리를 기르는데, 방마다 소가 정확히 한 마리씩 들어가도록 만들려고 한다. 그런데 소들은 아무 문 앞에나 줄을 서 버렸고, 한 문 앞에 여러 마리가 몰린 경우도 있다. $i$ 번 방의 바깥 문 앞에 선 소는 정확히 $c_i$ 마리이고, $\sum c_i = n$ 이다. 각 $c_i$ 는 0 이상의 정수이다.

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

입력

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

출력

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

예제3

예제 1
입력
```
10
1
0
0
2
0
0
1
2
2
2
```
예상 출력
```
33
```
예제 2
입력
```
3
1
1
1
```
예상 출력
```
0
```
예제 3
입력
```
3
3
0
0
```
예상 출력
```
5
```