과자의 분할

길이가 $N$인 막대 모양 과자가 있다. 이 과자는 길이 $1$짜리 조각 $N$개가 한 줄로 붙어 있는 형태이며, 인접한 두 조각 사이에는 모두 $N-1$개의 절단 지점이 있다. 각 절단 지점을 자르는 데 필요한 힘은 지점마다 다를 수 있다.

성관이와 도토리는 이 과자를 여러 조각으로 잘라, 각자가 가져가는 조각들의 길이 합이 정확히 $N/2$가 되도록 나눠 먹으려 한다. 서로 다른 사람이 가져갈 두 조각이 맞닿는 지점은 반드시 잘라야 하지만, 한 사람이 통째로 가져갈 부분 안쪽은 자를 필요가 없다.

각 지점을 자르는 데 필요한 힘이 주어질 때, 두 사람이 과자를 이 조건대로 나누기 위해 필요한 힘의 합의 최솟값을 구하라.

예를 들어 길이가 $6$인 과자가 있고 왼쪽에서부터 각 지점을 자르는 데 필요한 힘이 차례로 ${1, 8, 12, 6, 2}$라면, 아래 그림처럼 잘랐을 때 필요한 힘의 합이 $7$로 가장 작다.

첫째 줄에 과자의 길이 $N$이 주어진다. ($2 \le N \le 10{,}000$, $N$은 짝수)

둘째 줄부터 $N$번째 줄까지, 왼쪽에서부터 각 절단 지점을 자르는 데 필요한 힘 $P$가 한 줄에 하나씩 주어진다. ($0 \le P \le 10{,}000$)

필요한 힘의 합의 최솟값을 한 줄에 출력한다.