201231: [AtCoder]ARC123 B - Increasing Triples

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

Given are three sequences of $N$ integers each: $A = (A_1, \ldots, A_N),\,B = (B_1, \ldots, B_N),\,C = (C_1, \ldots, C_N)$.

You can permute each of these sequences in any way you like. Find the maximum possible number of indices $i$ such that $A_i < B_i < C_i$ after permuting them.

Constraints

  • $1\leq N\leq 10^5$
  • $1\leq A_i, B_i, C_i\leq 10^9$

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 answer.


Sample Input 1

5
9 6 14 1 8
2 10 3 12 11
15 13 5 7 4

Sample Output 1

3

We should permute them as follows:

  • $A = (1,6,8,9,14)$,
  • $B = (3,2,10,12,11)$,
  • $C = (4,7,15,13,5)$.

Then, we will have three indices $i$ ($i = 1, 3, 4$) such that $A_i < B_i < C_i$.


Sample Input 2

1
10
20
30

Sample Output 2

1

Sample Input 3

3
1 1 1
1 1 2
2 2 2

Sample Output 3

0

Input

题意翻译

### 题目描述 $ N $ 项组成的整数列 $ A = \ (A _ 1 \ \ldots, \ A_N), \, B = \ (B _ 1 \ \ldots, \ B_N), \, C = \ (C _ 1, \ \ldots, \ C_N) $。 你可以对数列进行排序。输出排序后 $ A_i \ <\ B_i \ <\ C_i $ 中满足 $ i $ 的最多个数。 ### 输入格式 输入以以下格式。 > $ N $ > > $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ > > $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $ > > $ C_1 $ $ C_2 $ $ \ldots $ $ C_N $ ### 输出格式 输出答案。 ### 说明/提示 **数据范围** - $ 1\leq\ N\leq\ 10^5 $ - $ 1\leq\ A_i,\ B_i,\ C_i\leq\ 10^9 $ **样例解释 $1$** 排序如下:-$ A = \ (1,6,8,9,14)$ - $ B = \ (3, 2, 10, 12, 11) $ - $ c = \ (4、7、15、13,5)$ 这个时候 $i$ 最多有 $3$ 个($i = \ 1,\ 3,\ 4 $)对 $ A_i \ <\ B_i \ <\ C_i $ 成立。

加入题单

上一题 下一题 算法标签: