题目描述

$(1,2,\cdots,N)$ の順列 $P=(P_1,P_2,\cdots,P_N)$ および $Q=(Q_1,Q_2,\cdots,Q_N)$ が与えられます．

すぬけくんは，$P$ と $Q$ から（連続するとは限らない）部分列を取り出そうとしています． ここで，取り出した部分列は以下の条件を満たす必要があります．

• $P$ から取り出した部分列と $Q$ から取り出した部分列の長さは等しい．以下，この長さを $k$ とおく．
• $P$ から取り出した部分列を $a=(a_1,a_2,\cdots,a_k)$，$Q$ から取り出した部分列を $b=(b_1,b_2,\cdots,b_k)$ とおく． このとき，各 $1\ \leq\ i\ \leq\ k$ について，$b_i$ は $a_i$ の倍数である．

すぬけ君が取り出せる部分列の長さの最大値を求めて下さい．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $P_1$ $P_2$ $\cdots$ $P_N$ $Q_1$ $Q_2$ $\cdots$ $Q_N$

输出格式

答えを出力せよ．

题目大意

【题目大意】

给定两个长度为 $n(n\le 2\times 10^5)$ 的 $1\sim n$ 的排列 $\text{P}$ 和 $\text{Q}$。

现在需要在 $\text{P}$ 和 $\text{Q}$ 中分别取出长度为 $k$ 两个子序列 $\text{A}$ 和 $\text{B}$，满足 $\forall i\in [1,k],a_i\mid b_i$。

最大化 $k$，求 $k$。

【输入格式】

共三行。

第一行一个整数 $n$。

第二行 $n$ 个整数表示排列 $\text{P}$。

第三行 $n$ 个整数表示排列 $\text{Q}$。

【输出格式】

一行一个整数 $k$ 表示答案。

4
3 1 4 2
4 2 1 3

2

5
1 2 3 4 5
5 4 3 2 1

3

10
4 3 1 10 9 2 8 6 5 7
9 6 5 4 2 3 8 10 1 7

6

提示

制約

• $1\ \leq\ N\ \leq\ 200000$
• $P$ は $(1,2,\cdots,N)$ の順列である
• $Q$ は $(1,2,\cdots,N)$ の順列である
• 入力される値はすべて整数である

Sample Explanation 1

$P$ から部分列 $(1,2)$ を，$Q$ から部分列 $(4,2)$ を取り出すと，これは条件を満たします． 長さ $3$ 以上の部分列を条件を満たすように取ることはできないため，答えは $2$ です．