Problems
The 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 data
First line contains the length n\:(1 \le n \le 1000) of the first sequence. Second line contains elements of the first sequence — integers no more than 10^4 by absolute value. Third line contains the length of the second sequence m\:(1 \le m \le 1000). Fourth line contains elements of the second sequence — integers no more than 10^4 by absolute value.
Output data
Print the length of the longest common subsequence, or 0 if it does not exist.
Examples
Input example #1
3 1 2 3 4 2 1 3 5
Output example #1
2
Input example #3
3 1 2 3 3 1001 1002 1003
Output example #3
0