4902. Permutation

单点时限: 5.0 sec

内存限制: 512 MB

Given three permutations of length $n$:

  • $A = {a_1, a_2, \cdots, a_n}$;
  • $B = {b_1, b_2, \cdots, b_n}$;
  • $C = {c_1, c_2, \cdots, c_n}$.

Find three subsequences:

  • $A’ = {a_{i_1}, a_{i_2}, \cdots, a_{i_m}}$;
  • $B’ = {b_{j_1}, b_{j_2}, \cdots, b_{j_m}}$;
  • $C’ = {c_{k_1}, c_{k_2}, \cdots, c_{k_m}}$.

The following conditions are satisfied:

  • Three subsequences with equal length;
  • $i_1 < i_2 < \cdots < i_m$,$j_1 < j_2 < \cdots < j_m$,$k_1 < k_2 < \cdots < k_m$;
  • For any $t \in [1, m]$ that satisfies $a_{i_t} = b_{j_t} \times c_{k_t}$ holds or $b_{j_t} = a_{i_t} \times c_{k_t}$ holds or $c_{k_t} = a_{i_t} \times b_{j_t}$.

Find the length of the longest subsequence that can be selected to satisfy the condition.

输入格式

The first line of an integer $n$ represents the length of the arrangement.

The next three rows of $n$ integers each represent the permutations $A, B$ and $C$ respectively.

输出格式

One integer in a row represents the length of the longest subsequence.

样例

Input
6
1 2 3 4 5 6
3 4 2 1 6 5
2 4 3 5 6 1
Output
3

提示

$1 \le n \le 20000$, $1 \le a_i, b_i, c_i \le n$.

Note that for any $1\le i,j\le n,i\ne j$, $\ a_i\ne a_j, b_i\ne b_j , c_i\ne c_j$ holds.

Sample explanation:

A legal subsequence is taken as

1 2 5
4 6 5
4 3 1

8 人解决,21 人已尝试。

8 份提交通过,共有 74 份提交。

7.8 EMB 奖励。

创建: 1 月,1 周前.

修改: 1 月,1 周前.

最后提交: 4 周,1 天前.

来源: N/A

题目标签