题目描述

A 和 B 在玩一个射击游戏，战场由若干单位正方形积木组成。积木占据了连续的若干列，且图形周长等于它最小包围矩形的周长。下图（a）是一个合法的战场，但（b）和（c）都不是：（b）中有空列；（c）的图形周长为 $14$，而最小包围矩形（用虚线画出）的周长为 $12$。受重力影响，每个积木的正下方要么是地面，要么是另一个积木。为了让战场看上去错落有致、玩着更刺激，它不能恰好是一个矩形（即，不能每列积木都一样高）。

游戏规则如下：

1. A 和 B 轮流射击，A 先射击。
2. 每次射击时，首先选择一行（该行必须至少有一个积木），以及「左」和「右」中的一个方向，然后往这个方向开火。子弹的威力为 $1 ～ 3$ 的均匀随机整数（即，威力为 $1,2,3$ 的概率各为 $1 \over 3$），表示子弹能打掉的积木个数，被打掉的积木将直接从战场中消失。如果该行的积木个数小于威力值，则子弹将在打掉该行所有积木后消失。例如，若选择往右射击从下往上数第 $3$ 行，且成力为 $2$，且这一行一共有 $4$ 个积木，则最左边的两个积木将被打掉。注意：这两个积木可以不连续。
3. 每次射击完成后，悬空的积木垂直往下落。所有积木不再下落后，下一位选手才能开始射击。
4. 谁打掉了最后一个积木，谁就获胜。

假定 A 和 B 都足够聪明，采取让自己获胜概率尽量高的策略，你的任务是计算出 A 获胜的概率。

输入格式

输入文件最多包含 $25$ 组测试数据，每个数据仅包含两行，第一行是整数 $n$ ，即积木的列数。第二行包含 $n$ 个正整数 $h_1,h_2,\dots,h_n$ ，表示从左往右数第 $i$ 列的高度。积木的排列方式保证符合题目描述（即：图形周长等于它最小包围矩形的周长，且各列的高度不全相同）。 $n=0$ 表示输入结束，你的程序不应当处理这一行。

输出格式

对于每组数据，输出仅一行，即 A 获胜的概率，四舍五入保留六位小数。

3
2 1 1
0

0.555556

数据规模与约定

$100\%$ 的数据满足：$1 \le n,h_i \le 6$。

提示

湖南省第六届大学生计算机程序设计竞赛

题目来源

鸣谢刘汝佳先生授权使用