CF10D LCIS（增强数据）

题目描述

本题与在线竞赛中的某题不同。

如果对于所有 $i < n$，都有 $a_i < a_{i+1}$，则称序列 $a_1, a_2, \ldots, a_n$ 为递增序列。

如果存在一组下标 $1 \leq i_1 < i_2 < \ldots < i_k \leq n$，使得 $a_{i_j} = s_j$，则称序列 $s_1, s_2, \ldots, s_k$ 是序列 $a_1, a_2, \ldots, a_n$ 的子序列。换句话说，序列 $s$ 可以通过从序列 $a$ 中删除某些元素得到。

现在给定两个整数序列。请你找出它们的最长公共递增子序列，即长度最大的递增序列，且该序列同时是两个序列的子序列。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 10000$），表示第一个序列的长度。
第二行包含 $n$ 个用空格分隔的整数，范围为 $[0, 10^9]$，表示第一个序列的元素。
第三行包含一个整数 $m$（$1 \leq m \leq 10000$），表示第二个序列的长度。
第四行包含 $m$ 个用空格分隔的整数，范围为 $[0, 10^9]$，表示第二个序列的元素。

输出格式

第一行输出 $k$，即最长公共递增子序列的长度。
第二行输出该子序列本身，元素之间用空格分隔。如果有多种方案，输出任意一种均可。

输入输出样例 #1

输入 #1

7
2 3 1 6 5 4 6
4
1 3 5 6

输出 #1

3
3 5 6

输入输出样例 #2

输入 #2

5
1 2 0 2 1
3
1 0 1

输出 #2

2
0 1

说明/提示

由 ChatGPT 4.1 翻译