원형 건물

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

📃 해결할 문제

현대 건축의 거장인 건축가 박승훈은 완벽한 원형의 건물을 새로 지었습니다. 내부에는 건물의 둘레 주위에 시계 방향으로 1부터 n까지 번호가 매겨진 n개의 방이 있습니다(3 ≤ n ≤ 1,000). 각 방에는 두 개의 인접한 방으로의 문과 건물의 외부로 열리는 문이 있습니다.

승훈은 각 방 i에 정확히 r_i명의 사람들이 있기를 원합니다(1 ≤ r_i ≤ 100). 질서정연하게 사람들을 건물 안으로 안내하기 위해, 그는 하나의 외부 문을 잠금 해제하여 사람들이 그 문을 통해 들어올 수 있게 할 계획입니다. 각각의 사람은 시계 방향으로 방을 걸어 적합한 목적지에 도달할 때까지 이동합니다. 승훈은 그의 사람들이 총 이동 거리를 최소로 만들 수 있게 하는 최적의 문을 잠금 해제하려고 합니다. 그가 가장 적절한 문을 잠금 해제했을 때, 사람들이 걸어야 할 최소 총 거리를 결정해 주십시오. 한 사람이 걸어야 하는 거리는 그가 통과하는 내부 문의 수입니다.

💻 입력

첫 번째 입력 줄에는 n이 있습니다. 나머지 n 줄 각각에는 r_1 ... r_n이 포함되어 있습니다.

🖨️ 출력

사람들이 전체적으로 이동해야 하는 최소 총 거리를 출력해주세요.

💻 예제 입력 1

🖨️ 예제 출력 1

💡 힌트

승훈이 이동하게 할 사람들의 수와 각 방에 필요한 사람 수는 다음과 같습니다:

첫 번째 방: 4명
두 번째 방: 7명
세 번째 방: 8명
네 번째 방: 6명
다섯 번째 방: 4명

이제 우리의 목표는 각 방에 필요한 사람 수만큼 사람들이 들어갈 때까지 어떤 방의 외부 문을 열어야 전체 이동 거리가 최소가 되는지 결정하는 것입니다.

사람들이 두 번째 방의 외부 문을 통해 들어오게 되면:

첫 4명의 사람들은 바로 첫 번째 방으로 이동합니다.
그 다음 7명의 사람들은 바로 두 번째 방으로 이동합니다.
그 다음 8명의 사람들은 두 번째 방에서 세 번째 방까지 이동합니다.
그 다음 6명의 사람들은 두 번째 방에서 네 번째 방까지 이동합니다.
마지막 4명의 사람들은 두 번째 방에서 다섯 번째 방까지 이동합니다.

이 때의 총 이동 거리를 계산하면:
4×1+7×0+8×1+6×2+4×3=4+0+8+12+12=36

하지만, 여기에 추가로 첫 4명이 세 번째, 네 번째, 다섯 번째 방을 통과하여 첫 번째 방으로 돌아오는 거리가 추가됩니다.
4×3=12

따라서, 두 번째 방의 외부 문을 열었을 때 총 이동 거리는
36+12=48이 됩니다.

출처: USACO 2016 February Contest, Bronze Problem 2. Circular Barn