Similarity

In modern application systems, recommendation systems are very widely used to recommend books, music, ads, items, and so on. A recommendation system needs to attract other users by providing the most interesting items to each user. One way of recommending is to find the user most similar 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$ is the number of items. It denotes a list of the preference magnitudes of the user for items. 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)$, and 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 their similarity.

Your program reads 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 the range $[0, 10^6]$ that represent a sequence.

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