Safe Gambling

A roulette wheel has $N = 2K + 1$ pockets arranged in a circle. The number of pockets $N$ is always odd, and pocket $i$ has a price $c_i$. The pockets lie on a circle, so the last pocket is adjacent to the first one.

A single bet covers exactly $K$ consecutive pockets on the wheel, and the price of that bet is the sum of the prices of the $K$ pockets it covers.

To cover every pocket you must place exactly three bets. Because $N = 2K + 1$ is odd, two bets of $K$ pockets always leave one pocket uncovered, while three bets can cover the whole wheel (even though some pockets may then be covered more than once).

Place three bets that together cover all pockets so that the sum of the three bet prices is as small as possible. A pocket covered by several bets is counted once for each bet that covers it. Output this minimum total price.

The input contains several roulettes. Each roulette is described on two lines.

The first line contains one odd integer $N = 2K + 1$ ($3 \le N < 200,000$), the number of pockets on the wheel.

The second line contains $N$ integers $c_0, c_1, \dots, c_{N-1}$ ($0 \le c_i \le 1000$), separated by spaces, giving the price of each pocket in the order they appear around the circle. The last pocket is adjacent to the first one.

The line after the last roulette contains a single $0$, which marks the end of the input.

For each roulette, print on its own line the minimum price of a set of bets satisfying all of the following:

1. It contains exactly three bets.
2. Each bet covers $K$ consecutive pockets.
3. The three bets together cover every pocket of the wheel (some pockets may be covered twice).
4. The sum of the three bet prices is the minimum over all such sets.

The price of a bet is the sum of the prices of the individual pockets it covers.