J. Beautiful Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A beautiful sequence is defined as a nonempty sequence that does not contain duplicate numbers, and the difference between the maximum and minimum values of the sequence is $$$k-1$$$, where $$$k$$$ is the length of the sequence. For example, $$$[1]$$$ and $$$[6, 4, 3, 5]$$$ are beautiful sequences, while $$$[2, 3, 2]$$$ and $$$[6, 9, 5, 8]$$$ are not.

There are two permutations, both of which contain $$$n$$$ distinct numbers from $$$1$$$ to $$$n$$$. As a sequence enthusiast, Alice wants to know how many beautiful sequences appear as subsequences in both permutations at the same time.

A sequence $$$s$$$ is a subsequence of a sequence $$$t$$$ if $$$s$$$ can be obtained from $$$t$$$ by deletion of several (possibly, zero or all) elements.

Input

The first line contains an integer $$$ n $$$ $$$(1 \leq n \leq 100000)$$$ — the length of these two permutations.

The second line contains $$$n$$$ distinct integers, representing the first permutation.

The third line contains $$$n$$$ distinct integers, representing the second permutation.

Output

An integer representing the number of the beautiful sequences appear as subsequences in both permutations at the same time.

Example
Input
4
2 4 1 3
4 2 3 1
Output
7
Note

In the test case, the beautiful sequences that meet the condition are $$$[1]$$$, $$$[2]$$$, $$$[3]$$$, $$$[4]$$$, $$$[2,1]$$$, $$$[2,3]$$$, $$$[4,3]$$$.