e-olymp
Competitions

Azerbaijan Programming Olympiad - 2nd Stage preparation

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 (1n1000) 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 (1m1000). 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
1 2 3
4
2 1 3 5
Output example #1
2