Longest Common Palindromic Subsequence

Given two sequences of integers, your task is to compute the length of the Longest Common Palindromic Subsequence (LCPS) between them. A palindromic sequence is one that reads the same forwards and backwards. Formally, if (S) is a subsequence of the first sequence, and (S) is palindromic and appears as a subsequence in the second sequence, then the length of (S) is a candidate. The LCPS is the candidate with the maximum length.

A key observation is: a subsequence (S) is a palindrome if and only if (S = S^R) (i.e. (S) is equal to its reversal). Therefore, one approach to compute the LCPS is to obtain the reversal of the second sequence and compute the Longest Common Subsequence (LCS) between the first sequence and this reversed sequence, which will yield the result.

Your solution must read the input from standard input (stdin) and output the answer to standard output (stdout).

inputFormat

The first line contains an integer (n) indicating the number of elements in the first sequence. The second line contains (n) space-separated integers. The third line contains an integer (m) indicating the number of elements in the second sequence. The fourth line contains (m) space-separated integers. (n) or (m) may be zero. In that case, the respective sequence is empty (the corresponding line may be empty).

outputFormat

Output a single integer which is the length of the Longest Common Palindromic Subsequence (LCPS) of the two sequences.## sample

4
1 2 3 4
4
3 2 1 3

3