射击游戏

地面上摆放着若干积木，共有 $n$ 列。第 $i$ 列从地面起连续摆放了 $h_i$ 块积木。初始图形的周长等于其最小包围矩形的周长，且各列高度不全相同。

A 和 B 进行射击游戏，A 先手，双方轮流行动。每次行动时，当前玩家先选择一个至少含有一块积木的水平行，并选择从左向右或从右向左射击。随后，本次射击的威力 $p$ 随机确定为 $1$ 、 $2$ 、 $3$ 之一， $3$ 种结果等概率出现。

子弹从所选方向沿该行前进，按照遇到积木的顺序击落至多 $p$ 块积木。若该行的积木少于 $p$ 块，则击落该行的全部积木；同一行中的空位不会阻挡子弹。射击结束后，失去支撑的积木会竖直下落，因此每个被击中的列的高度都会相应减少 $1$ 。

击落场上最后一块积木的玩家获胜。假设双方都采用使自己获胜概率最大的策略，请求出 A 最终获胜的概率。

输入格式

输入文件最多包含 $25$ 组测试数据。

每组测试数据包含 $2$ 行。第 $1$ 行包含一个整数 $n$ ，表示积木的列数。第 $2$ 行包含 $n$ 个正整数 $h_1,h_2,\ldots,h_n$ ，其中 $h_i$ 表示从左向右数第 $i$ 列的高度。

输入保证积木的排列符合题目描述，即初始图形的周长等于其最小包围矩形的周长，且各列高度不全相同。

当输入的 $n=0$ 时，表示输入结束，无须处理该行。

对于每组测试数据，输出一行 A 获胜的概率，四舍五入保留 $6$ 位小数。

3
2 1 1
0

0.555556

本题为湖南省第六届大学生计算机程序设计竞赛试题「射击游戏」，题面与测试数据整理自 BZOJ。

3
2 1 1
0

0.555556