Tree Count

Time limit1sMemory limit512 MB

Summary

Given a DFS ordering and a BFS ordering of a rooted tree's vertices, find the average height over all rooted trees that produce both orderings.

Level: Hard8 of 10
Topics: Tree, DFS, BFS, Dynamic programming
Solved: No attempts yet

Problem

A rooted tree can be traversed with depth-first search (DFS) and breadth-first search (BFS) to obtain the DFS and BFS orderings of its vertices. Two different trees can have the same DFS ordering, and their BFS orderings can also be the same. For example, the two trees below both have DFS ordering 1 2 4 5 3 and BFS ordering 1 2 3 4 5.

Given a DFS ordering and a BFS ordering, find the average height of all rooted trees that have both orderings. If $K$ different rooted trees have both orderings and their heights are $h_1, h_2, \ldots, h_K$ , output $(h_1 + h_2 + \cdots + h_K)/K$ .

Input

The first line contains a single integer $n$ , the number of vertices. The second line contains $n$ integers from 1 to $n$ , the DFS ordering. The third line contains $n$ integers from 1 to $n$ , the BFS ordering. At least one tree has both orderings.

Output

Print one real number, the average height of the trees. An answer is accepted if its absolute error is at most 0.001. A tree with one vertex has height 1. Otherwise, its height is 1 plus the maximum height among the subtrees rooted at its children.

Constraints

$2 \le n \le 200000$

Examples1

Example 1
Input
```
5
1 2 4 5 3
1 2 3 4 5
```
Expected output
```
3.500
```