# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Marks Crisis!!!

By shihan04 · 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


• BinarySearch

### Statistics

75% Solution Ratio

dip_BRUREarliest, Apr '20

skmonirFastest, 0.0s

CodefresherLightest, 918 kB

mdalaminislamShortest, 447B

### Submit 