AT_xmascon22_c.Conditional Swap

给定 $ (1,2,\ldots,N) $ 的排列 $ P=(P_1,P_2,\ldots,P_N) $ 和 $ Q=(Q_1,Q_2,\ldots,Q_N) $。请判断能否通过不超过 $ N^2 $ 次如下操作，将 $ P $ 变为 $ Q $，如果可以，请给出一种操作序列。

• 每一次可以选择一个整数 $ i $，使得下述条件至少满足一项，并交换 $ P_i $ 与 $ P_{i+1} $ 的值。
  • $ 1 \leq i \leq N-2 $ 且 $ \min(P_i,P_{i+1}) < P_{i+2} < \max(P_i,P_{i+1}) $
  • $ 2 \leq i \leq N-1 $ 且 $ \min(P_i,P_{i+1}) < P_{i-1} < \max(P_i,P_{i+1}) $

输入按以下格式给出：

$ N $ $ P_1 $ $ P_2 $ $ \cdots $ $ P_N $ $ Q_1 $ $ Q_2 $ $ \cdots $ $ Q_N $

如果可以将 $ P $ 变为 $ Q $，按以下格式输出操作序列：

$ k $ $ i_1 $ $ i_2 $ $ \cdots $ $ i_k $

其中 $ k $ 是操作的次数（$ 0 \leq k \leq N^2 $），$ i_j $ 表示第 $ j $ 次操作选择 $ i=i_j $。

如果不能将 $ P $ 变为 $ Q $，输出 -1。

数据范围

• $ 2 \leq N \leq 1000 $
• $ (P_1,P_2,\ldots,P_N) $ 是 $ (1,2,\ldots,N) $ 的一个排列。
• $ (Q_1,Q_2,\ldots,Q_N) $ 是 $ (1,2,\ldots,N) $ 的一个排列。

由 ChatGPT 5 翻译