문제
길이 N mm(밀리미터)의 막대 모양의 과자가 1개 있다. (여기서 N은 짝수). 2명의 JOI 관계자가 이 과자를 여러개로 잘라서, N/2 mm 씩 나눠가지기로 했다.
이유는 모르지만 이 과자는 장소에 따라서 절단하기 쉬운 정도가 다르다. 두사람은 과자의 맨 왼쪽부터 1mm씩 관찰하여, 각 위치를 절단하는데 몇 초가 걸리는지 측정했다.
두사람이 과자를 나누기 위해서 걸리는 초수의 최소값을 구하는 프로그램을 작성하라.
입력
입력의 1행에는, 막대모양과자의 길이 N(2≤N≤10,000, 단 N은 짝수)가 써있다.
입력의 i+1행에는 (1≤i≤N-1), 왼쪽부터 i mm째의 장소를 절단할때 걸리는 초수를 나타내는 정수 ti(1≤ti≤10,000)가 써있다. 절단가능한 장소가 N-1개소가 있으니 주의해라.
출력
두명이 과자를 나누기 위해 절단하는데 걸린 최소 시간(초단위)를 한줄에 출력한다.
예제
6
1
8
12
6
2
7
힌트
태그
로그인해야 코드를 작성할 수 있어요.