Dividing Subsequence

AtCoder

IDarc133_b

Time5000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

4
3 1 4 2
4 2 1 3

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$.

Input #2

5
1 2 3 4 5
5 4 3 2 1

Output #2

Input #3

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

Output #3

API Response (JSON)

{
  "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 subseq...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments