Hide

Problem C
Bílskúrar

Languages en is
/problems/bilskurar/file/statement/en/img-0001.jpg
Image from wikimedia.org

Hannes lives in Brúnaland. In Brúnaland there is only one road and all the houses are on one side of the road. On the other side of the road there are garages, one for each house. The houses are numbered and the garage corresponding to house $i$ is also numbered $i$.

It would of course be natural if the houses and garages were numbered in increasing order. But Brúnaland is not engineered that well, so the numbering is all over the place.

When homeowners travel between their house and their garage they go in a straight line. This can cause collisions. How many pairs of homeowners could potentially collide when traveling from their homes to their garages?

Input

The first line of the input contains a single integer $n$ ($1 \leq n \leq 2\cdot 10^5$), the number of houses on the streets. The second line of the input contains $n$ integers, the $i$-th of which corresponds to the number on the $i$-th house. The second line of the input contains $n$ integers, the $i$-th of which corresponds to the number on the $i$-th garage. Each house number and each garage number is at least $1$ and not larger than $n$ and appears precisely once in each line.

Output

Print a single integer, the number of possible collisions.

Explanation of Sample Input

The first sample case falls under scoring group $3$. The figure shows the path the homeowners travel from their house to their garages, with possible collisions marked in red.

\includegraphics[width=0.5\textwidth ]{sample_illustration}
Figure 1: Sample $1$

Scoring

Group

Points

Constraints

1

20

$1 \leq n \leq 10$ and the houses are numbered in increasing order

2

20

$1 \leq n \leq 10^3$ and the houses are numbered in increasing order

3

20

$1 \leq n \leq 10^3$

4

20

The houses are numbered in increasing order

5

20

No further constraints

Sample Input 1 Sample Output 1
5
1 3 2 5 4
2 1 3 4 5
3
Sample Input 2 Sample Output 2
4
1 2 3 4
4 3 2 1
6
Sample Input 3 Sample Output 3
7
3 5 2 7 6 4 1
3 5 2 7 6 4 1
0

Please log in to submit a solution to this problem

Log in