题目背景

Rebirth.

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

题目描述

圆，焰，光在观看赛狗游戏。

三个人都猜测了狗冲过终点的顺序，即 $P_i$ 表示第 $i$ 只冲过终点的狗的编号。我们假设没有平局。

有 $N$ 条狗，因此 $P_i$ 构成一个 $1\sim N$ 的排列。不妨记第 $j$ 个人猜测的排列为 $P(j)$。

此外，最终狗冲过终点的顺序构成排列 $T$。

计算满足以下条件的数对 $(a,b)$ 的数量：

• $1\le a\lt b\le N$；
• 在 $T$ 中，$a$ 在 $b$ 前面；
• $\forall 1\le j\le 3$，要么 $a$ 在所有的 $P(j)$ 中都在 $b$ 前面，要么 $b$ 在所有的 $P(j)$ 中都在 $a$ 前面。

输入格式

第一行，一个正整数 $N$。

第二行，$N$ 个正整数描述 $T$。

接下来三行，第 $j$ 行 $N$ 个正整数，描述 $P(j)$。

输出格式

输出一行一个整数，即答案。

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

提示

样例解释

样例 $1$ 解释：只有 $(2,3)$ 满足条件。

数据范围

对于 $100\%$ 的数据，保证：

• $2\le N\le 5\times 10^5$；
• $\forall 1\le j\le 3$，$P(j)$ 构成一个 $1\sim N$ 的排列。
• $T$ 构成一个 $1\sim N$ 的排列。

子任务编号	$N\le$	特殊性质	得分
$1$	$5\, 000$	无	$7$
$2$	$5\times 10^5$	有	$8$
$3$	$5\times 10^4$	无	$29$
$4$	$5\times 10^5$		$56$

特殊性质：$P(1)=P(2)$。也就是说圆和焰猜的排列是一样的。