색상환 2 timer 1s memory 128MB

가난한 예술가 홍윤이는 그림을 그리고 있다.

홍윤이는 어느 날 놀라운 아이디어가 떠올라 새로운 그림을 그리기로 했다.

홍윤이는 새로운 그림을 위해 준혁이의 물감 가게에 가서 물감을 사려고 한다.

준혁이의 물감 가게는 물감을 색상환 모양으로 정렬해 판매하고 있다.

총 N개의 물감이 진열되어 있으며 N은 1보다 큰 홀수이다.

색깔은 1번부터 N번까지 시계방향으로 번호가 붙어 있고 N번 물감 다음은 1번 물감이다.

i번 물감은 한 통에 A_i원으로 판매되고 있다. (0 \le A_i \le 1000)

그런데 준혁이의 가게는 비슷한 색깔을 같이 구매해야 하는 굉장히 특이한 판매 방식을 가지고 있다.

구체적으로 항상 연속한 K개의 물감을 한 통씩 묶음으로만 판매하는데 이때 N = 2K+1이다.

즉, 물감을 살 때는 항상 전체의 절반 (홀수이므로 정확히 절반은 아니지만) 만큼을 인접하게 골라서 사야한다.

이때 묶음의 가격은 구매하는 모든 물감 가격의 합만큼이다.

홍윤이는 그림에 모든 물감을 한 통씩 쓰려고 한다.

하지만 홍윤이는 가난하기 때문에 최대한 적은 돈으로 물감을 사고 싶다.

N과 모든 A_i가 주어지면 모든 물감을 적어도 한 통씩 구매하는 최소의 비용을 계산해보자!