这个问题与在线竞赛中的问题不同。
如果 ai < ai + 1 并且 i < n,则序列 a1, a2, ..., an 称为递增序列。
如果存在一组索引 1 ≤ i1 < i2 < ... < ik ≤ n 且 aij = sj,则序列 s1, s2, ..., sk 称为序列 a1, a2, ..., an 的子序列。换句话说,可以通过删除序列a中的一些元素来导出序列s。
给定两个整数序列。您要找到它们的最长公共递增子序列,即最大长度的递增序列,它是两个序列的子序列。
输入
第一行包含一个整数 n (1 ≤ n ≤ 500) — 第一个序列的长度。第二行包含 n 个空格分隔的整数,范围为 [0, 109]——第一个序列的元素。第三行包含一个整数 m (1 ≤ m ≤ 500) — 第二个序列的长度。第四行包含 m 个以空格分隔的整数,范围为 [0, 109]——第二个序列的元素。
输出
第一行输出 k — 最长公共递增子序列的长度。在第二行中输出子序列本身。用空格分隔元素。如果有多个解,则输出任意一个。
示例
输入 #1
7 2 3 1 6 5 4 6 4 1 3 5 6
输出 #1
3 3 5 6
输入 #2
5 1 2 0 2 1 3 1 0 1
输出 #2
2 0 1