C - Made Up Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

1 以上 N 以下の整数からなる長さ N の数列 A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N), C = (C_1, C_2, \dots, C_N) が与えられます。

1 以上 N 以下の整数 i, j の組 (i, j) であって、A_i = B_{C_j} となるものの総数を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq A_i, B_i, C_i \leq N
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
C_1 C_2 \ldots C_N

出力

A_i = B_{C_j} となる (i, j) の総数を出力せよ。


入力例 1

3
1 2 2
3 1 2
2 3 2

出力例 1

4

条件を満たす組は (1, 1), (1, 3), (2, 2), (3, 2)4 つです。


入力例 2

4
1 1 1 1
1 1 1 1
1 2 3 4

出力例 2

16

全ての組が条件を満たします。


入力例 3

3
2 3 3
1 3 3
1 1 1

出力例 3

0

条件を満たす組は存在しません。

Score : 300 points

Problem Statement

Given are three sequences of length N each: A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N), and C = (C_1, C_2, \dots, C_N), consisting of integers between 1 and N (inclusive).

How many pairs (i, j) of integers between 1 and N (inclusive) satisfy A_i = B_{C_j}?

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq A_i, B_i, C_i \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
C_1 C_2 \ldots C_N

Output

Print the number of pairs (i, j) such that A_i = B_{C_j}.


Sample Input 1

3
1 2 2
3 1 2
2 3 2

Sample Output 1

4

Four pairs satisfy the condition: (1, 1), (1, 3), (2, 2), (3, 2).


Sample Input 2

4
1 1 1 1
1 1 1 1
1 2 3 4

Sample Output 2

16

All the pairs satisfy the condition.


Sample Input 3

3
2 3 3
1 3 3
1 1 1

Sample Output 3

0

No pair satisfies the condition.