We know that a rooted tree can be traversed using Depth-First Search (DFS) and Breadth-First Search (BFS) to generate its DFS order and BFS order, respectively. Two different trees may have the same DFS order, and they may also have the same BFS order. For example, the two trees shown below both have the DFS order 1 2 4 5 3 and the BFS order 1 2 3 4 5.

Given a DFS order and a BFS order, we want to find the average height of all rooted trees that satisfy these conditions. That is, if there are $K$ different rooted trees that have this specific DFS order and BFS order, and their heights are $h_1, h_2, \dots, h_K$, please output:

\begin{equation} \frac{h_1 + h_2 + \dots + h_K}{K} \end{equation}

Input

The first line contains one positive integer $n$, representing the number of nodes in the tree.

The second line contains $n$ positive integers, which is a permutation of $1 \sim n$, representing the DFS order of the tree.

The third line contains $n$ positive integers, which is a permutation of $1 \sim n$, representing the BFS order of the tree.

It is guaranteed that at least one tree exists that matches the given two sequences.

Output

Output a single real number, rounded to exactly three decimal places, representing the average height of the trees.

Examples

Input 1

5 
1 2 4 5 3 
1 2 3 4 5

Output 1

3.500

Constraints

If the difference between your output and the standard output is no more than $10^{-3}$, you will receive points for that test case; otherwise, you will receive no points.

$20\%$ of the test data satisfies: $n \leq 10$;

$40\%$ of the test data satisfies: $n \leq 100$;

$85\%$ of the test data satisfies: $n \leq 2000$;

$100\%$ of the test data satisfies: $2 \leq n \leq 200000$.

Note

Tree height: If a rooted tree contains only one root node, its height is $1$. Otherwise, its height is the maximum height of all subtrees of the root node plus $1$.

For any three nodes $a, b, c$ in the tree, if $a$ and $b$ are both children of $c$, then the relative order of $a$ and $b$ in the BFS order and the DFS order is consistent; that is, either $a$ is before $b$ in both, or $a$ is after $b$ in both.