23245번 - Similarity 다국어

문제

In modern application systems, a recommendation system is very widely used to recommend books, music, ads, items, etc. The recommendation system needs to attract other users by providing the most interested items to each user. One way of recommendation is to find the most similar user to the current user, then recommend the items that the most similar user purchased to the current user. To help the recommendation system, we design a similarity measure. A user is represented by a sequence $p = p_1, p_2, \dots, p_n$ where $n$ denotes the number of items. It denotes a list of the preference magnitudes of the user for items. When we are given two sequences $p = p_1, p_2, \dots, p_n$ and $q = q_1, q_2, \dots, q_n,ドル a similar tuple is defined as a tuple $(i, j, k)$ such that $p_i < p_j < p_k$ and $q_i < q_j < q_k$. For given two sequences $p = p_1, p_2, \dots, p_n$ and $q = q_1, q_2, \dots, q_n,ドル the similarity is defined as the number of similar tuples.

For example, if the given two sequences are $p = 2, 5, 9, 5, 1$ and $q = 1, 4, 5, 3, 2,ドル the similar tuples are $(1, 2, 3),ドル $(1, 4, 3),ドル $(5, 2, 3),ドル and $(5, 4, 3)$ The similarity of the two sequences is 4ドル$.

Given two sequences $p = p_1, p_2, \dots, p_n$ and $q = q_1, q_2, \dots, q_n,ドル write a program to output the similarity of them.

입력

Your program is to read from standard input. The input starts with a line containing one integer $n$ (1ドル \le n \le 100,000$), where $n$ is the length of a sequence. In the following two lines, each line contains $n$ integers in range $[0, 10^6]$ that represent a sequence.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the similarity of the two sequences.

제한

힌트