Genome Evolution

Time limit1sMemory limit128 MB

Summary

Count the shared gene blocks of length above one that appear as consecutive runs in both chromosomes.

Level: Medium6 of 10
Topics: Intervals, Array
Solved: No attempts yet

Problem

Xi is a developmental biologist who studies developmental distances between chromosomes. In Xi's simplified view a chromosome is a permutation of $n$ genes numbered $1$ to $n$ . Xi is building a measure of evolutionary distance between two chromosomes. In Xi's theory of evolution, any set of genes that lies together in both chromosomes is a positive witness that the two chromosomes are similar.

A positive witness is a pair of sequences $A$ and $A'$ of the same length, where $A$ is a consecutive subsequence of the first chromosome, $A'$ is a consecutive subsequence of the second chromosome, and $A$ is a permutation of $A'$ . Each chromosome contains every gene exactly once, so once $A$ is fixed there is at most one matching $A'$ . Count the positive witnesses of the two given chromosomes whose length is greater than one.

Input

The input contains several test cases. Each test case starts with a line containing the number of genes $n$ ( $2 \le n \le 3000$ ). The next two lines contain the two chromosomes, one per line, each as a list of positive integers that uses every number from $1$ to $n$ exactly once. A line containing a single $0$ ends the input and is not a test case.

Output

For each test case, print one line with the number of positive witnesses for the two chromosomes.

Examples2

Example 1

Input

Expected output

3
10

Example 2
Input
```
2
1 2
2 1
3
1 2 3
3 2 1
0
```
Expected output
```
1
3
```