#ABC077C. 斯努凯祭坛

斯努凯祭坛

AT_arc084_a [ABC077C] Snuke Festival

题目描述

\hspace{15pt}今年的すぬけ祭又到了。りんごさん打算首先进行すぬけ君召唤仪式。该仪式需要一个祭坛,而祭坛由上部、中部和下部三个类别的零件各一个组成。

\hspace{15pt}每个类别的祭坛零件各有 nn 个。第 ii 个上部零件的尺寸为 aia_i,第 ii 个中部零件的尺寸为 bib_i,第 ii 个下部零件的尺寸为 cic_i。

\hspace{15pt}制造祭坛时,中部零件的尺寸必须严格大于上部零件的尺寸,下部零件的尺寸必须严格大于中部零件的尺寸。反之,只要满足这些条件,任意三个零件都可以组合成一个祭坛。

\hspace{15pt}询问りんごさん最多可以制造多少种不同的祭坛。两种祭坛被认为不同,当且仅当三部分零件中至少有一个不同。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦105)n \left(1 \leqq n \leqq 10^5\right) 代表每个类别的零件数量。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表每个上部零件的尺寸。

\hspace{15pt}第三行输入 nn 个整数 $b_1, b_2, \dots, b_n \left(1 \leqq b_i \leqq 10^9\right)$ 代表每个中部零件的尺寸。

\hspace{15pt}第四行输入 nn 个整数 $c_1, c_2, \dots, c_n \left(1 \leqq c_i \leqq 10^9\right)$ 代表每个下部零件的尺寸。

输出格式

\hspace{15pt}在一行上输出一个整数,代表りんごさん可以制造的不同祭坛的数量。

测试样例

2
1 5
2 4
3 6
3

样例 1 解释

\hspace{15pt}可以制造如下 33 种祭坛:

∙ \hspace{23pt}\bullet\,上部使用第 11 个零件、中部使用第 11 个零件、下部使用第 11 个零件;

∙ \hspace{23pt}\bullet\,上部使用第 11 个零件、中部使用第 11 个零件、下部使用第 22 个零件;

∙ \hspace{23pt}\bullet\,上部使用第 11 个零件、中部使用第 22 个零件、下部使用第 22 个零件。

3
1 1 1
2 2 2
3 3 3
27

样例 2 解释

\hspace{15pt}三类零件各有 33 个,且上部尺寸恒为 11、中部恒为 22、下部恒为 33,任意一个上部、中部、下部零件的组合都满足严格递增,因此共有 3×3×3=273 \times 3 \times 3 = 27 种祭坛。

6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288
87