题目描述

足够聪明的 Alice 和 Bob 在玩一种棋盘游戏。这个游戏需要用到一个有 $(n+1)$ 个格子的长条棋盘，按从左到右的顺序给每个格子编号 $0, 1, \cdots, n$。除了编号为 $n$ 的格以外，每一格都有两个数 $p_i, q_i$。游戏开始前，将一个棋子放在第 $0$ 格。游戏由二人轮流操作，这里我们不妨假设 Alice 先手。

轮到其中一位玩家进行操作时，这位玩家可以根据当前格子的 $p$ 值决定前进的步数。具体地说，假设当前棋子位于第 $k$ 格，那么当前进行操作的玩家可以将棋子向前移动 $x$ 格，其中 $x$ 可以是满足 $1\le x\le p_k$ 的任意整数。如果玩家没有走满 $p_k$ 格，即 $x<p_k$，那么该玩家可以在完成移动后选择是否进行一次挑战。如果选择不进行挑战，那么由另一位玩家进行下一轮操作。否则，如果当前玩家选择挑战，那么系统将会产生两个随机整数 $u$ 和 $v$，其中：$u$ 表示挑战的能量，它在 $\left[1, p_k-x\right]$ 中等概率产生；$v$ 表示挑战所需的活化能，它在 $\left[0, q_k + q_{k+x}\right]$ 中等概率产生。根据 $u$ 和 $v$ 的值，系统会根据以下规则自动判定挑战结果：

如果 $u>v$，则挑战成功，对方玩家的操作被跳过一轮，由当前玩家继续操作； 如果 $u=v$，则挑战结果为平手，什么事情都不会发生，由对方玩家进行操作； 如果 $u<v$，则挑战失败，当前玩家下一轮操作将会被跳过，即对方玩家可以连续操作两轮。 为了防止其中一方玩家一直被跳过，规定：

如果当前玩家通过自身的挑战获得额外操作机会，则该玩家在该额外操作机会中不能进行第二次挑战； 如果当前玩家通过对方玩家的挑战获得额外操作机会，则该玩家不能在其第一次操作结束时发起挑战，只能在第二次操作结束时选择是否进行挑战，并且当且仅当挑战成功时可以进行第三次操作。 需要注意的是，无论连续进行多少次操作，每次操作都需要将棋子向前移动至少 $1$ 格。同大多数游戏一样，谁将棋子移动到终点（即编号为 $n$ 的格）谁就获胜。

Alice 和 Bob 都足够聪明，可以心算出对于当前棋子的位置，能使自己获胜概率最大的操作。作为一名旁观者，你没有他们那么强的心算能力；但是你也想通过自己编程的能力，计算出当 Alice 先手从第 $0$ 格开始进行操作时，Alice 的胜率。

输入格式

输入的第一行包含一个正整数 $n$，表示棋盘包含 $(n+1)$ 格，分别标号 $0, 1, \cdots, n$。

输入的第二行包含 $n$ 个正整数 $p_0, p_1, \cdots, p_{n-1}$，分别表示第 $0$ 格至第 $(n-1)$ 格的 $p$ 值。

输入的第三行包含 $n$ 个正整数 $q_0, q_1, \cdots, q_{n-1}$，分别表示第 $0$ 格至第 $(n-1)$ 格的 $q$ 值。

输出格式

输出一个实数，表示 Alice 先手开始游戏的胜率。当你的输出与标准输出的绝对误差不超过 $10^{-6}$ 时，我们认为你的输出是正确的。

3
3 3 3
1 2 3

1.000000000000000000

3
2 3 3
1 2 3

0.250000000000000000

10
2 1 4 7 4 8 3 6 4 8
3 1 4 1 5 9 2 6 5 3

0.833333333333333333

提示

【样例解释 1】

Alice 先手，由于可以直接从第 $0$ 格移动到终点的第 $3$ 格，Alice 会直接将棋子移动到第 $3$ 格，故 Alice 必胜。

【样例解释 2】

Alice 先手，但是不能直接移动到第 $3$ 格，并且无论结束操作时棋子在第 $1$ 格还是第 $2$ 格，Bob 都可以直接将其移动到终点的第 $3$ 格，因此 Alice 必须尝试挑战。将棋子移动到第 $1$ 格并发动挑战，挑战成功的概率为 $1/4$，故 Alice 的胜率为 $1/4$。

【数据范围】

对于 $100\%$ 的数据，保证 $1\le n\le 100000$，$1\le p_i, q_i\le 333$。