Background

Rebirth.

Translated from Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection) D2T3。$\texttt{1s,0.5G}$。

Problem Description

Three people are watching a greyhound racing game.

Each of them guesses the order in which the dogs cross the finish line. Let $P_i$ be the ID of the dog that finishes in the $i$-th place. We assume there are no ties.

There are $N$ dogs, so $P_i$ forms a permutation of $1\sim N$. Let the permutation guessed by the $j$-th person be $P(j)$.

Also, the actual finishing order forms a permutation $T$.

Compute the number of pairs $(a,b)$ that satisfy the following conditions:

• In $T$, $a$ is before $b$.
• $\forall 1\le j\le 3$, either $a$ is before $b$ in all $P(j)$, or $b$ is before $a$ in all $P(j)$.

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ positive integers describing $T$.

The next three lines: the $j$-th line contains $N$ positive integers describing $P(j)$.

Output Format

Output one line with one integer, the answer.

3
2 3 1
1 2 3
1 2 3
2 3 1

1

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

0

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

3

Hint

Sample Explanation

For sample $1$, only $(2,3)$ satisfies the conditions.

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $2\le N\le 5\times 10^5$.
• $\forall 1\le j\le 3$, $P(j)$ is a permutation of $1\sim N$.
• $T$ is a permutation of $1\sim N$.

Special property: $P(1)=P(2)$. That is, the first two people guessed the same permutation.

Translated by ChatGPT 5