P11197 [COTS 2021] Greyhound Racing Game Tiket

Rebirth. Translated from [Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2021/) D2T3。$\texttt{1s,0.5G}$。

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)$.

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 one line with one integer, the answer.

#### 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$. | Subtask ID | $N\le $ | Special Property | Score | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 5\, 000 $ | None | $ 7 $ | | $ 2 $ | $ 5\times 10^5 $ | Yes | $ 8 $ | | $ 3 $ | $ 5\times 10^4$ | None | $ 29 $ | | $ 4 $ | $ 5\times 10^5 $ | None | $ 56 $ | Special property: $P(1)=P(2)$. That is, the first two people guessed the same permutation. Translated by ChatGPT 5