eolymp
bolt
Try our new interface for solving problems
Problems

The Longest Common Subsequence

The Longest Common Subsequence

Time limit 1 second
Memory limit 128 MiB

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