Limits 1s, 512 MB

Rakib got the result of his previous English exam. But he did very poor in the exam, and went to his English teacher to increase his marks.

There was a question in the exam where Rakib had to rearrange $n$ sentences to make a valid story. The correct answer was the sequence $ A_1, A_2, \dots, A_n $ but Rakib wrote the sequence $ B_1, B_2, \dots, B_n $. The teacher was supposed to give 1 mark for each $i$ such that $A_i = B_i (1 \leq i \leq n)$. But because of Rakib's request, the teacher asked Rakib to find a common subsequence between his answer and the correct one. His marks will then be equal to the length of the common subsequence he finds.

As Rakib wants the highest marks possible, he has to find the longest common subsequence. Since he is really foolish, he wants you to help him.

Input

First you will be given an integer $n$ ($1\leq n\leq 10^5$) — the number of sentences in the sequence.The next line will contain $n$ integers $A_i$ ($1\leq A_{i},i\leq n$). Next line will also contain $n$ integers $B_j$ ($1\leq B_{j},j\leq n$).

Output

Print a single integer which indicates the highest possible marks that Rakib can obtain.

Samples

InputOutput
8
2 4 3 5 6 1 8 7
2 8 4 3 5 6 7 1
6
InputOutput
5
1 2 3 4 5
3 4 1 2 5
3

Submit

Login to submit.

Statistics

77% Solution Ratio
dip_BRUREarliest, Apr '20
nusuBotFastest, 0.0s
CodefresherLightest, 918 kB
mdalaminislamShortest, 447B
Toph uses cookies. By continuing you agree to our Cookie Policy.