Longest Common Subsequence

Given two sequences of integers A and B, your task is to determine the length of their Longest Common Subsequence (LCS).

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

You can solve this problem using dynamic programming. One common recurrence relation is given by:

$$\text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1] + 1, & \text{if } A[i-1] = B[j-1],\\ \max(\text{dp}[i-1][j],\ \text{dp}[i][j-1]), & \text{otherwise}. \end{cases} $$

The final answer will be in dp[n][m], where n and m are the lengths of sequences A and B respectively.

This problem is a classic exercise in computing the LCS and will help you master dynamic programming techniques.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n representing the length of the first sequence.
• The second line contains n space-separated integers representing the elements of the first sequence A.
• The third line contains an integer m representing the length of the second sequence.
• The fourth line contains m space-separated integers representing the elements of the second sequence B.

outputFormat

Output a single integer (to stdout) which is the length of the longest common subsequence of sequences A and B.

## sample

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

4