A carousel holds n token stacks arranged in a circle, each with a positive integer size. Because they sit in a ring, stack i is adjacent to stack i+1, and the last stack is also adjacent to the first. You combine them into a single stack by repeatedly merging two currently-adjacent stacks (adjacency is on the ring, so a wrap-around merge of the current first and last stacks is allowed) into one stack whose size is their sum. Each merge costs the size of the newly formed stack.

Report the minimum total cost to reduce the ring to a single stack.

Input format

Line 1: an integer n, the number of stacks. Line 2: n space-separated positive integers, the stack sizes in clockwise order.

Output format

A single integer: the minimum total merging cost (0 if there is only one stack).

Constraints

• 1 <= n <= 150
• 1 <= each stack size <= 1000

3
1 2 3

9

1
5

0