Magic Sticks#2287
Magic was regarded by ancient peoples as a means to obtain the help of divine powers. In a well-known story, a group of sorcerers threw their staffs on the ground, which miraculously turned into live snakes. In response, another person threw his staff, which turned into a snake that devoured the snakes of the magicians!
The only magic you need for this task is to solve it. You are given a magic stick composed of several straight segments, with hinges between them that allow the stick to be folded. Depending on the segment lengths and the way they are folded, it is possible to obtain various polygons. You should determine the maximum area that can be enclosed by polygons formed by folding the stick in this way. Each segment may be included in at most one polygon. Segments can only touch at their endpoints. For example, the stick shown below consists of five segments and four hinges, and it can be folded to produce the polygon shown at the right.
The input consists of several test cases. Each test describes a magic stick. The first line of each test contains the number of segments (1 \le n \le 500) in the magic stick. The next line contains integers S_1, S_2, \ldots, S_n (1 \le S_i \le 1000), which are the lengths of the segments in the order they appear in the stick.
The last test is followed by a line containing a single zero.
For each test, output its number and the maximum possible area of a closed region that can be obtained by folding the magic stick at the given points. Answers with an absolute or relative error not exceeding 10^{-4} will be accepted.
The output format is shown in the sample.
Example 1