Longest Common Subsequence (LCS)

Given two sequences of integers, your task is to compute the length of their Longest Common Subsequence (LCS). A subsequence is a sequence that appears in the same relative order in both sequences but not necessarily contiguously.

The LCS is defined using the following recurrence relation in dynamic programming:

\( dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{if } seq1[i-1] = seq2[j-1] \\ \max(dp[i-1][j],\, dp[i][j-1]), & \text{otherwise} \end{cases} \)

Your program must read from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input consists of four lines:

1. An integer n representing the number of elements in the first sequence.
2. n space-separated integers representing the first sequence.
3. An integer m representing the number of elements in the second sequence.
4. m space-separated integers representing the second sequence.

All input is provided via stdin.

outputFormat

Output a single integer, the length of the longest common subsequence (LCS), to stdout.

6
1 2 3 4 1
5
3 4 1 2 1 3

3