PEG Judge - WC01 - S - Big Brother

Woburn Challenge 2001 - Suicidal

Wednesday Night - Big Brother

It's Wednesday night and the remaining frosh (the ones that haven't been kicked off) are having a little fun inside the Waterloo compound (ie. inside the convex polygonal fence previously described) arranged by their frosh leaders as a way to unwind. They are divided into groups and each group is given a map of the fence. Each vertex of the fence has a number on it and they are told the following things.

Along the path connecting any 2 vertices, there are exactly F tokens (where F is the multiplicative product of the 2 numbers on the end vertices). Each token entitles the group to have an extra ½ hour of fun during the week. The goal is to divide the entire intra-fence region into triangles in the following way:

The vertices of the triangles have to be vertices of the original polygonal fence.
The triangles that the group chooses to form are determined by which paths the group decides to choose (the paths mark the sides of the triangle). If they choose a path, they pick up all the tokens on that path. Clearly, since the vertices of the triangles have to be vertices of the original fence, the group cannot choose 2 paths that cross each other.

See the accompanying drawing for an example of a correct triangulation (shown in bold).

These are all the instructions that the group is given. What they don't know is that this is not really a game. They are being watched by the leaders to determine which group will triangulate the field by choosing paths that allow them to pick up the least number of tokens, i.e. which group will decide to have the least fun. The leaders realize that all good engineers eschew fun and thus, the groups that instinctively choose to have the least fun are best qualified for the program. The rest are kicked out.

You are in one of these groups. You don't like fun (hey, you're writing this contest on a summer day, aren't you?) and want to determine the least amount of fun your group can have, i.e. what is the least number of tokens that a group can pick up and still triangulate the field.

Input

N (number of vertices in the fence; -1 denotes end of input; N ≤ 100).
The next line will contain F_i, the numbers assigned to the j^th vertex. 0 < F_i ≤ 10 000 (natural numbers).