Alice 非常热爱体操表演，最近她又在平衡木进行训练。

为了加强 Alice 的训练热情，Bob 决定和 Alice 玩一个游戏，并通过游戏给 Alice 一些奖励。这个奖励取决于最终成功跳下平衡木的位置。平衡木上从左向右的位置记为  0,1,\ldots,N+1  。如果 Alice 到达了位置  0  或是  N+1  ，她就会从平衡木的一端掉下去，遗憾地得不到奖励。

如果 Alice 处在一个给定的位置  k  ，她可以进行下面两项中的任意一项：

投掷一枚硬币。如果背面朝上，她前往位置  k-1  ，如果正面朝上，她前往位置  k+1  （也就是说，每种可能性  1/2  的概率）。

跳下平衡木，获得  f(k)  的奖励。

Alice 意识到她并不能保证结果能够得到某一特定数量的奖励，这是由于她的移动是由随机的掷硬币结果控制。然而，基于她的起始位置，她想要求出当她进行一系列最优的决定之后，她能够得到的期望奖励（“最优”指的是这些决定能够带来最高可能的期望奖励）。

期望奖励的定义：假设 Alice 能有 "\frac{1}{3}" 的概率得到 9 的奖励，"\frac{1}{2}" 的概率得到 6 的奖励，"\frac{1}{6}"的概率得到 12 的奖励，那么她的期望奖励是：\frac{1}{3}*9+\frac{1}{2}*6+\frac{1}{6}*12=8 。