두 순열의 최장 공통 부분 수열

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제다.

예를 들어 [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3]이고, 그 크기는 2다.

1부터 $N$까지의 정수가 각각 정확히 한 번씩 등장하는 두 수열 $A$와 $B$가 주어진다. 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.

첫째 줄에 두 수열의 크기 $N$ ($1 \le N \le 100{,}000$)이 주어진다.

둘째 줄에 수열 $A$의 원소 $N$개가, 셋째 줄에 수열 $B$의 원소 $N$개가 공백으로 구분되어 주어진다.

두 수열의 LCS 크기를 한 줄에 출력한다.