/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
(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 の倍数である．
すぬけ君が取り出せる部分列の長さの最大値を求めて下さい．
制約
- 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
P から部分列 (1,2) を，Q から部分列 (4,2) を取り出すと，これは条件を満たします． 長さ 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
Score : 500 points
Problem Statement
Given are permutations P=(P_1,P_2,\cdots,P_N) and Q=(Q_1,Q_2,\cdots,Q_N) of (1,2,\cdots,N).
Snuke is going to extract (not necessarily contiguous) subsequences from P and Q. Here, the subsequences must satisfy the conditions below.
- The length of the subsequence extracted from P and that extracted from Q are the same. Below, let k be this length.
- Let a=(a_1,a_2,\cdots,a_k) and b=(b_1,b_2,\cdots,b_k) be the subsequences extracted from P and Q, respectively. Then, for each 1 \leq i \leq k, b_i is a multiple of a_i.
Find the maximum possible length of each subsequence extracted by Snuke.
Constraints
- 1 \leq N \leq 200000
- P is a permutation of (1,2,\cdots,N).
- Q is a permutation of (1,2,\cdots,N).
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \cdots P_N Q_1 Q_2 \cdots Q_N
Output
Print the answer.
Sample Input 1
4 3 1 4 2 4 2 1 3
Sample Output 1
2
If we extract the subsequence (1,2) from P and (4,2) from Q, they satisfy the conditions. It is impossible to extract subsequences of length 3 or greater to satisfy the conditions, so the answer is 2.
Sample Input 2
5 1 2 3 4 5 5 4 3 2 1
Sample Output 2
3
Sample Input 3
10 4 3 1 10 9 2 8 6 5 7 9 6 5 4 2 3 8 10 1 7
Sample Output 3
6