← 返回题目列表

AtCoder · arc133_b

B. 划分子序列

中文机器翻译题面 查看原题

分数: 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