Longest Common Subsequence(LCS) of Two Permutations

By a clever transformation, the classic LCS problem is converted to an LIS problem, thereby reducing the time complexity.

Given two permutations P1 and P2 of 1, 2, …, n, find their longest common subsequence(LCS), n <= 10⁵.

For example, input: The first line contains an integer n. The next two lines each contain a permutation of n natural numbers from 1 to n.

5 
3 2 1 4 5
1 2 3 4 5

So you need to output:

3

Because the length of the LCS (1, 4, 5 or 3, 4, 5or 2, 4, 5 )of these two permutations is 3.

The question is from Codeforces: https://codeforces.com/gym/102951/problem/C