Description

Given two permutations $P_1$ and $P_2$ of $1,2,\ldots,n$, find their longest common subsequence.

Input Format

The first line contains an integer $n$. Each of the next two lines contains $n$ integers forming a permutation of $1,2,\ldots,n$.

Output Format

A single integer, the length of the longest common subsequence.

5 
3 2 1 4 5
1 2 3 4 5

3

Hint

• For $50\%$ of the testdata, $n \le 10^3$.
• For $100\%$ of the testdata, $n \le 10^5$.

Translated by ChatGPT 5