解题思路

因为 $p,q$ 都是 $1\sim n$ 的排列，所以每个数字只出现一次。

设数字 $x$ 在排列 $p$ 中的位置为 $posP[x]$，在排列 $q$ 中的位置为 $posQ[x]$。

如果一个序列是公共子序列，那么它对应的每个数字在两个排列中的出现位置都必须同时严格递增。

现在题目要求的是：在所有公共子序列中，找到字典序最大的那一条。

题目内容

给定两个长度为 $n$ 的排列 $p$ 和 $q$ (均为 $1$ ~ $n$ 的一个排列，元素两两不同)，请你在它们的公共子序列中，找到一条字典序最大的序列并输出。

名词解释:

【字典序】对两序列从左到右比较第一个不同的元素，较大者字典序更大;若一个序列是另一个序列的前缀，则更长的序列字典序更大。

【子序列】子序列为从原序列中删除任意个(可以为零、可以为全部)元素得到的新序列。

【数组公共子序列】如果数组 $a$ 的一个子序列 $a'$ 与数组 $b$ 的一个子序列 $b'$ 完全相等，那么子序列 $a',b'$ 是数组 $a,b$ 的一个公共子序列。

输入描述

第一行输入一个整数 $n(1≤n≤2×10^5)$，表示排列的长度。

第二行输入 $n$ 个整数 $p_1,p_2,...,p_n$，表示排列 $p$。

第三行输入 $n$ 个整数 $q_1,q_2,...,q_n$，表示排列 $q$

保证 $p$ 与 $q$ 都是 $1$~$n$ 的排列。

输出描述

第一行输出一个整数 $k$，表示答案序列的长度。

第二行输出 $k$ 个整数，为这条字典序最大的公共子序列。

样例1

输入

5
2 5 3 1 4
5 2 4 3 1

输出

2
5 4

说明

两序列的公共子序列中，以 $5$ 开头后，能够继续选择的最大元素为得到 [$5,4$]。与 [$5,1$] 相比，第二个元素更大，因此 [$5,4$] 的字典序更大