Splitting the Snack

There is a stick-shaped snack of length $N$. The snack is made of $N$ unit-length pieces glued in a row, so there are $N-1$ cut points, one between each pair of adjacent pieces. The force needed to cut through a point may differ from point to point.

Seonggwan and Dotori want to cut the snack into several pieces and share it so that the total length each person takes is exactly $N/2$. A point where two pieces going to different people meet must be cut, but there is no need to cut anywhere inside a stretch that a single person takes whole.

Given the force required at each cut point, find the minimum possible total force needed to divide the snack this way.

For example, suppose the snack has length $6$ and the forces required to cut each point, from left to right, are ${1, 8, 12, 6, 2}$. Then cutting as shown below gives the smallest possible total force, $7$.

The first line contains the length of the snack $N$. ($2 \le N \le 10{,}000$, and $N$ is even.)

From the second line through the $N$-th line, the force $P$ needed to cut each point, from left to right, is given one per line. ($0 \le P \le 10{,}000$)

Print the minimum total force required, on a single line.