유사도

현대의 응용 시스템에서 추천 시스템은 책, 음악, 광고, 상품 등을 추천하는 데 매우 널리 쓰인다. 추천 시스템은 각 사용자에게 가장 관심 있을 항목을 제공해서 다른 사용자를 끌어들여야 한다. 추천하는 방법 중 하나는 현재 사용자와 가장 유사한 사용자를 찾은 다음, 그 사용자가 구매한 항목을 현재 사용자에게 추천하는 것이다. 추천 시스템을 돕기 위해 유사도 척도를 설계한다.

사용자는 수열 $p = p_1, p_2, \dots, p_n$ 로 표현된다. 여기서 $n$ 은 항목의 수다. 이 수열은 항목에 대한 사용자의 선호도 크기 목록을 나타낸다. 두 수열 $p = p_1, p_2, \dots, p_n$ 과 $q = q_1, q_2, \dots, q_n$ 이 주어졌을 때, 유사 튜플은 $p_i < p_j < p_k$ 이고 $q_i < q_j < q_k$ 인 튜플 $(i, j, k)$ 로 정의된다. 주어진 두 수열 $p = p_1, p_2, \dots, p_n$ 과 $q = q_1, q_2, \dots, q_n$ 에 대해 유사도는 유사 튜플의 개수로 정의된다.

예를 들어 주어진 두 수열이 $p = 2, 5, 9, 5, 1$ 이고 $q = 1, 4, 5, 3, 2$ 이면 유사 튜플은 $(1, 2, 3)$, $(1, 4, 3)$, $(5, 2, 3)$, $(5, 4, 3)$ 이고 두 수열의 유사도는 $4$ 다.

두 수열 $p = p_1, p_2, \dots, p_n$ 과 $q = q_1, q_2, \dots, q_n$ 이 주어졌을 때, 두 수열의 유사도를 출력하는 프로그램을 작성하라.

프로그램은 표준 입력에서 입력을 읽는다. 입력은 정수 $n$ ($1 \le n \le 100,000$) 이 포함된 한 줄로 시작한다. 여기서 $n$ 은 수열의 길이다. 이어지는 두 줄에는 각각 $[0, 10^6]$ 범위의 정수 $n$ 개가 수열을 나타내며 주어진다.

프로그램은 표준 출력에 출력을 쓴다. 정확히 한 줄을 출력한다. 그 줄에는 두 수열의 유사도가 있어야 한다.