Longest Common Subsequence of Two Permutations

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

Medium6Dynamic programmingBinary searchNo attempts yetTime limit2sMemory limit512 MB

Description

Examples4

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.