정올군의 기지는 완벽한 원형 모양으로 이루어져 있다.

기지의 내부는 주변 둘레를 따라 시계 방향으로 번호가 매겨진 N개의 방이 있으며, 방의 번호는 1부터 N까지다.

각 방은 두 개의 이웃 방으로 통하는 문과 외부로 통하는 문을 가지고 있다.

정올군의 보급 장교는 각 i번 방에 정확히 A_i 개의 도시락이 배급되기를 바란다.

보급을 위해 외부로 통하는 문을 여는 것은 보안을 위하여 딱 하나의 방에서만 허용이 된다.

도시락이 외부에서 하나의 방에 모두 들어가게 된다면, 이는 이웃 방으로 옮겨지는 것이 가능하다.

보급 장교는 도시락이 최소한의 거리를 이동하여 모든 방에 적절히 보급하기를 원한다.

이 때, 거리는 도시락이 통과하는 내부 문의 개수이다.

예를 들어 5개의 방이 있고 각 방이 받고자 하는 도시락 개수는 4 7 8 6 4 라고 하자.

전체 도시락 개수는 29이다.

1번 방에 29개의 도시락을 외부문을 이용하여 전달한 경우를 보자.

1) 1번 방에 4개의 도시락을 이동하는 거리는 0이다.

2) 2번 방에 7개의 도시락을 이동하는 거리는 1개의 내부 문을 통과하므로 7*1 = 7이다.

3) 3번 방에 8개의 도시락을 이동하는 거리는 2개의 내부 문을 통과하므로 8*2 = 16이다.

4) 4번 방에 6개의 도시락을 이동하는 거리는 2개의 내부 문을 통과하므로 6*2 = 12이다.

5) 5번 방에 4개의 도시락을 이동하는 거리는 1개의 내부 문을 통과하므로 4*1 = 4이다.

6) 따라서 이경우 거리의 합은 39이다.

2번 방에 놓는 경우는 생략하고 3번 방에 29개의 도시락을 외부문을 이용하여 전달한 경우를 보자.

1) 1번 방에 4개의 도시락을 이동하는 거리는 2개의 내부 문을 통과하므로 4*2 = 8이다.

2) 2번 방에 7개의 도시락을 이동하는 거리는 1개의 내부 문을 통과하므로 7*1 = 7이다.

3) 3번 방에 8개의 도시락을 이동하는 거리는 0개의 내부 문을 통과하므로 0이다.

4) 4번 방에 6개의 도시락을 이동하는 거리는 1개의 내부 문을 통과하므로 6*1 = 6이다.

5) 5번 방에 4개의 도시락을 이동하는 2개의 내부 문을 통과하므로거리는 4*2 = 8이다.

6) 따라서 이경우 거리의 합은 29이고 이것이 최소값이다.

모든 도시락을 N개의 방에 보급 장교의 계획대로 보급되기 위해
전체 도시락이 이동해야 하는 거리 합의 최소값을 구하여 출력하는 프로그램을 작성하시오.

보급 전략 timer 1s memory 512MB

보급 전략 1s 512MB