{"problem":{"name":"Dividing Subsequence","description":{"content":"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 subseq","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc133_b"},"statements":[{"statement_type":"Markdown","content":"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)$.\nSnuke is going to extract (not necessarily contiguous) subsequences from $P$ and $Q$. Here, the subsequences must satisfy the conditions below.\n\n*   The length of the subsequence extracted from $P$ and that extracted from $Q$ are the same. Below, let $k$ be this length.\n*   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$.\n\nFind the maximum possible length of each subsequence extracted by Snuke.\n\n## Constraints\n\n*   $1 \\leq N \\leq 200000$\n*   $P$ is a permutation of $(1,2,\\cdots,N)$.\n*   $Q$ is a permutation of $(1,2,\\cdots,N)$.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $\\cdots$ $P_N$\n$Q_1$ $Q_2$ $\\cdots$ $Q_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc133_b","tags":[],"sample_group":[["4\n3 1 4 2\n4 2 1 3","2\n\nIf 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$."],["5\n1 2 3 4 5\n5 4 3 2 1","3"],["10\n4 3 1 10 9 2 8 6 5 7\n9 6 5 4 2 3 8 10 1 7","6"]],"created_at":"2026-03-03 11:01:14"}}