Longest Common Subsequence

In this problem, you are given two sequences of integers. Your task is to compute the length of their Longest Common Subsequence (LCS). The LCS of two sequences is defined as the longest sequence that appears in both sequences (not necessarily consecutively).

The dynamic programming recurrence for the LCS is given by: [ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } arr1[i-1] = arr2[j-1] \ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases} ]

Use the above relation to build a DP table and the answer will be found in dp[n][m] where n and m are the lengths of the two sequences respectively.

Note: The input is taken from standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The input consists of four lines:

1. The first line contains an integer (N), the number of elements in the first sequence.
2. The second line contains (N) space-separated integers representing the first sequence.
3. The third line contains an integer (M), the number of elements in the second sequence.
4. The fourth line contains (M) space-separated integers representing the second sequence.

outputFormat

Output a single integer representing the length of the longest common subsequence between the two sequences.## sample

4
1 2 3 4
5
2 4 3 1 2

2