← 返回题目列表

Codeforces · 10/D

D. 最长公共递增子序列

中文机器翻译题面 查看原题

这个问题与在线竞赛中的问题不同。

如果 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