最长公共递增子序列

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

若一个序列的每个元素都严格小于下一个元素，则称它为严格递增序列。若可以从序列中删除若干元素而不改变剩余元素的相对顺序得到另一个序列，则后者是前者的子序列。

给定两个整数序列，请找出它们的最长公共递增子序列（LCIS）：该序列严格递增，同时是两个给定序列的子序列，并且长度最大。

输入格式

第一行包含整数 $n$。第二行包含 $n$ 个整数 $a_1,\ldots,a_n$。

第三行包含整数 $m$。第四行包含 $m$ 个整数 $b_1,\ldots,b_m$。

输出格式

第一行输出最长长度 $k$。第二行输出一个长度为 $k$ 的最长公共递增子序列。若有多种方案，输出任意一种。

当 $k=0$ 时，第二行可以为空。

样例输入 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

数据范围

$1\le n,m\le500$，$0\le a_i,b_i\le10^9$。