Longest Common Subsequence of Two Permutations

Time limit2sMemory limit512 MB

Summary

Two permutations of 1 to N are given; find the length of their longest common subsequence.

Level: Medium6 of 10
Topics: Dynamic programming, Binary search
Solved: No attempts yet

Problem

The longest common subsequence (LCS) problem asks, for two given sequences, for the longest sequence that is a subsequence of both.

For example, the LCS of [1, 2, 3] and [1, 3, 2] is [1, 2] or [1, 3], and its size is 2.

You are given two sequences $A$ and $B$ in which every integer from 1 to $N$ appears exactly once. Write a program that computes the size of their LCS.

Input

The first line contains the size $N$ ( $1 \le N \le 100{,}000$ ) of both sequences.

The second line contains the $N$ elements of $A$ , and the third line contains the $N$ elements of $B$ , separated by spaces.

Output

Print the size of the LCS of the two sequences on one line.

Examples4

Example 1
Input
```
2
1 2
2 1
```
Expected output
```
1
```
Example 2
Input
```
3
1 2 3
1 3 2
```
Expected output
```
2
```
Example 3
Input
```
1
1
1
```
Expected output
```
1
```
Example 4
Input
```
5
1 2 3 4 5
1 2 3 4 5
```
Expected output
```
5
```