说明
F 正在尝试使用一个六面骰子独自玩双六。
在双六方格中,有两个选项:“前进○方格”和“回到起点”,如果你停在那里,你必须始终按照指示移动。如果您由于方块的效果而移动并最终停在再次具有该效果的方块处,请按照指示继续移动。
由于F很慢,所以实际玩双六变得很痛苦。因此,我们决定找到达到目标的掷骰子次数的期望值。
输入
输入由多个测试用例组成。输入的结尾由仅包含一个零的行表示。每个测试用例均按以下格式给出。
n x_1 x_2 … x_n
- 1≦n≦500,000
- -1≦x_i≦n-i
- x_1,x_n=0
测试用例1双六中的方格数显示在行中 写入n。对于鳟鱼 它的编号最大为1与n。起始正方形是1,然后按最接近开始的顺序排列。2番,3番,…,n-1目标方块继续。 号码是n。i在编号的方块上掷骰子 如果你投掷j, 移至方块i+j。如果 如果分数为i+j是 在n或更高,则视为已达到目标。 在
测试用例2行中,n整数 写入x_i。 代表写在第x_i是 它仅由i个方格中的指令。x_i = -1 然后,“回到开头。”0 < x_i ≦ n-i 然后“x_i继续前进”,x_i = 0 那么对该方格没有影响。
x_1, x_n 是 它仅由0有保证。给定的双六有可能达到目标,掷骰子次数的期望值为 保证该值不会超过10^7。每个文件的测试用例数量保证不超过300个。另外,对于每个文件n的总和保证小于或等于 500,000。
输出
对于每个测试用例,在一行上打印预期的骰子数量。该误差可以是绝对误差或相对误差。10^{-7}。
示例输入
2 0 0 7 0 -1 -1 -1 -1 -1 0 7 0 0 0 0 0 0 0 7 0 5 4 3 2 1 0 8 0 -1 -1 -1 0 -1 -1 0 0
示例输出 由
1.00000000 6.00000000 2.16139403 1.00000000 10.50000000