题目内容

给定两个长度均为 $n$ 的整数序列 $A$ 和 $B$，其中每个序列恰好包含 $1$ 到 $n$ 的每个整数各一次（顺序可以任意）。如果某个序列 $S$ 同时是 $A$ 和 $B$ 的子序列（子序列指从原序列删除任意个元素后得到的新序列），则称 $S$ 为 $A$ 与 $B$ 的一个“共同子序列”。在所有共同子序列中，我们希望找出一个在如下意义上“最大”的序列：对于两个序列，从左到右依次比较对应位置的元素，第一次出现不同时，元素较大者所对应的序列更大；若一个序列是另一个序列的前缀，则更长的序列更大。这种比较方式常称为字典序。请你求出字典序最大的共同子序列，并输出其内容和长度。

约束条件：序列长度 $n$ 满足 $1 \le n \le 2 \times 10^5$。两个序列中的元素均为 $1$ 到 $n$ 的整数，且每个数恰出现一次。

输入描述

第一行包含一个整数 $n$，表示序列的长度。第二行包含 $n$ 个用空格分隔的整数，表示序列 $A$。第三行包含 $n$ 个用空格分隔的整数，表示序列 $B$。

输出描述

第一行输出一个整数 $k$，表示字典序最大的共同子序列的长度。第二行输出 $k$ 个用空格分隔的整数，表示该序列的元素。

样例1

输入

3
1 2 3
1 3 2

输出

1
3

说明

数字 3 在序列 $A$ 中的位置为 $3$，在 $B$ 中的位置为 $2$，均满足起始条件（位置 $\ge 1$），因此被选中。选中后，后续可选位置变为 $i=4$，$j=3$。

数字 2 在 $A$ 中的位置为 $2$（小于 $i$）不可选；数字 1 在 $A$ 中的位置为 $1$（小于 $i$）不可选。最终得到的共同子序列为 $[3]$，长度为 1。虽然 $[1,3]$ 也是共同子序列且长度更长，但按照字典序规则，首位 3 大于 1，因此 $[3]$ 更大。

样例2

输入

4
4 1 3 2
1 4 2 3

输出

2
4 3

说明

从大到小扫描数字：

数字 4 在 $A$ 中位置 $1$，$B$ 中位置 $2$，均 $\ge 1$，选入答案，并更新 $i=2$，$j=3$。 数字 3 在 $A$ 中位置 $3$，$B$ 中位置 $4$，满足 $pos \ge i,j$，选入答案，更新 $i=4$，$j=5$。

数字 2 在 $A$ 中位置 $4$，$B$ 中位置 $3$，此时 $j=5$，不满足 $B$ 中位置条件；数字 1 也不满足。

最终得到 $[4,3]$，长度 2。字典序比较时，$[4,3]$ 比 $[4,2]$ 等序列大。

样例3

输入

1
1
1

输出

1
1

说明

只有唯一元素 1，其在两个序列中的位置都是 $1$，可以直接选择。长度为 1 的序列 $[1]$ 即为字典序最大的共同子序列。

样例4

输入

4
1 2 3 4
1 2 3 4

输出

1
4

说明

两个序列完全相同，整个序列 $[1,2,3,4]$ 是一个共同子序列。但贪心算法优先选择最大的数字 4，它在 $A$ 和 $B$ 中的位置均为 $4$，满足起始条件，被选为第一个元素。之后 $i$ 和 $j$ 变为 $5$，其余数字的位置均小于 $5$，无法再选，得到序列 $[4]$。

按照字典序比较规则，先比较第一位：$[4]$ 的第一位 4 大于 $[1,2,3,4]$ 的第一位 1，所以 $[4]$ 字典序更大。因此答案为 $[4]$，长度为 1。