分数: 500 点
问题陈述
给出的是排列 P=(P_1,P_2,\cdots,P_N) 和 Q=(Q_1,Q_2,\cdots,Q_N) of (1,2,\cdots,N).
Snuke 将从中提取(不一定是连续的)子序列 P 和 Q。 这里,子序列必须满足以下条件。
- 提取的子序列的长度 P 以及提取自 Q 是相同的。下面,让 k 就是这个长度。
- 让 a=(a_1,a_2,\cdots,a_k) 和 b=(b_1,b_2,\cdots,b_k) 是从中提取的子序列 分别是 P 和 Q。 然后,对于每个 1 \leq i \leq k, b_i 是的倍数 a_i.
求 Snuke 提取的每个子序列的最大可能长度。
约束
- 1 \leq N \leq 200000
- P 是一个排列 (1,2,\cdots,N).
- Q 是一个排列 (1,2,\cdots,N).
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \cdots P_N Q_1 Q_2 \cdots Q_N
输出
打印答案。
示例输入 1
4 3 1 4 2 4 2 1 3
示例输出 1
2
如果我们提取子序列 (1,2) 来自 P 和 (4,2) 来自 Q,他们满足条件。 不可能提取长度的子序列 3 或更大以满足条件,所以答案是 2.
示例输入 2
5 1 2 3 4 5 5 4 3 2 1
示例输出 2
3
示例输入 3
10 4 3 1 10 9 2 8 6 5 7 9 6 5 4 2 3 8 10 1 7
示例输出 3
6