Problem Description

Alice and Bob, who are smart enough, are playing a board game. The game uses a long board with $(n+1)$ cells. Number the cells from left to right as $0, 1, \cdots, n$. Except for the cell numbered $n$, each cell has two numbers $p_i, q_i$. Before the game starts, place a piece on cell $0$. The two players take turns to operate; assume Alice moves first.

When it is a player's turn, the player can decide how many steps to move forward based on the current cell's $p$ value. Specifically, suppose the piece is currently on cell $k$. Then the current player may move the piece forward by $x$ cells, where $x$ can be any integer satisfying $1 \le x \le p_k$. If the player does not move the full $p_k$ cells, i.e. $x < p_k$, then after the move the player may choose whether to start a challenge. If they choose not to challenge, then the other player takes the next turn. Otherwise, if the current player chooses to challenge, the system generates two random integers $u$ and $v$, where:

• $u$ is the energy of the challenge. It is generated uniformly at random in $\left[1, p_k - x\right]$.
• $v$ is the activation energy required for the challenge. It is generated uniformly at random in $\left[0, q_k + q_{k+x}\right]$.

Based on the values of $u$ and $v$, the system determines the outcome automatically using the following rules:

• If $u > v$, the challenge succeeds. The other player's next turn is skipped, and the current player continues to operate.
• If $u = v$, the challenge is a draw. Nothing happens, and the other player operates next.
• If $u < v$, the challenge fails. The current player's next turn will be skipped, i.e. the other player can operate for two consecutive turns.

To prevent one player from being skipped forever, the following rules apply:

• If the current player gains an extra operation opportunity through their own challenge, then in that extra opportunity they cannot start a second challenge.
• If the current player gains an extra operation opportunity through the other player's challenge, then they cannot start a challenge at the end of their first operation. They may only choose whether to challenge at the end of their second operation, and they can make a third operation if and only if the challenge succeeds.

Note that no matter how many consecutive operations occur, in each operation the piece must be moved forward by at least $1$ cell. As in most games, whoever moves the piece to the terminal cell (the cell numbered $n$) wins.

Both Alice and Bob are smart enough to compute mentally, for the current position of the piece, the operation that maximizes their probability of winning. As an observer, you are not as good at mental calculation as they are; however, you want to use programming to compute Alice's winning probability when Alice moves first starting from cell $0$.

Input Format

The first line contains a positive integer $n$, indicating that the board has $(n+1)$ cells, numbered $0, 1, \cdots, n$.

The second line contains $n$ positive integers $p_0, p_1, \cdots, p_{n-1}$, representing the $p$ values of cells $0$ to $(n-1)$.

The third line contains $n$ positive integers $q_0, q_1, \cdots, q_{n-1}$, representing the $q$ values of cells $0$ to $(n-1)$.

Output Format

Output a real number representing Alice's winning probability when Alice moves first. Your output is considered correct if its absolute error compared with the standard output does not exceed $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

Hint

[Sample Explanation 1]

Alice moves first. Since she can move directly from cell $0$ to the terminal cell $3$, Alice will move the piece directly to cell $3$, so Alice will surely win.

[Sample Explanation 2]

Alice moves first, but she cannot move directly to cell $3$. Also, no matter whether the piece ends the operation on cell $1$ or cell $2$, Bob can move it directly to the terminal cell $3$. Therefore, Alice must attempt a challenge. If she moves the piece to cell $1$ and starts a challenge, the probability that the challenge succeeds is $1/4$, so Alice's winning probability is $1/4$.

[Constraints]

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 100000$ and $1 \le p_i, q_i \le 333$.

Translated by ChatGPT 5