Average Tree Height from DFS and BFS Orders

We are given the DFS and BFS orders of a rooted tree. Note that two different trees may have the same DFS order and also the same BFS order. For example, the following two trees 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, your task is to find the average height of all rooted trees that yield these orders. Suppose there are $$K$$ different trees with heights $$h_1, h_2, \ldots, h_K$$. You need to output the average height:

The height of a tree is defined as the number of nodes on the longest path from the root to any leaf (a tree with one node has height 1).

inputFormat

The first line contains an integer $$n$$, the number of nodes in the tree. The second line contains $$n$$ space‐separated integers representing the DFS order of the tree. The third line contains $$n$$ space‐separated integers representing the BFS order of the tree.

outputFormat

Output the average height of all trees that yield the given DFS and BFS orders. Your answer is accepted if its absolute or relative error does not exceed $$10^{-6}$$.

sample

5
1 2 4 5 3
1 2 3 4 5

3.5