A and B are playing a shooting game on a battlefield consisting of square-shaped unit blocks. The blocks are occupying some consecutive columns, and the perimeter of the figure equals the perimeter of its minimal bounding box. The figure (a) below is a valid battlefield, but (b) and (c) are not, because in (b), there is an empty column; in (c), the perimeter of figure is 14, but the perimeter of the bounding box (drawn with dashed lines) is 12. With the help of gravity, each block is either located on another block, or sitting on the ground. To make the battlefield look more exciting, it must not be a perfect rectangle (i.e. it is not allowed that every column has the same height) Here is the rule of the game:
2/2 Assume Alice and Bob are both very clever (always follows the strategy that maximizes the proba- bility he/she wins), what is the probability that Alice wins? Input There will be at most 25 test cases, each with two lines. The first line is a single integer n (1 ≤ n ≤ 6), the number of columns. The second line contains n integers h1, h2, ..., hn (1 ≤ hi ≤ 6), the heights of the columns from left to right. The battlefield is guaranteed to satisfy the restrictions in the problem (perimeter of figure equals that of the minimal bounding box, and is not a perfect rectangle). Input is terminated by n = 0. Output For each test case, print a single line, the probability that A wins, to six decimal points. Sample Input 3 211 0 Sample Output 0.555556