Competitions

# Sequences + Longest Common Subsequence

# The Longest Common Subsequence

Two sequences of integers are given. Find the length of their longest common subsequence (the subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements).

#### Input

The first line contains the length **n** (**1** ≤ **n** ≤ **1000**) of the first sequence. The second line contains the elements of the first sequence - the integers no more than **10000** by absolute value. The third line contains the length of the second sequence **m** (**1** ≤ **m** ≤ **1000**). The forth line contains the elements of the second sequence - the integers no more than **10000** by absolute value.

#### Output

Print the length of the longest common subsequence, or **0** if it does not exist.

Input example #1

3 1 2 3 4 2 1 3 5

Output example #1

2