题目描述

小 I 与小 J 正在玩一个叫做“开火车”，又称作“拖板车”和“小猫钓鱼”的扑克游戏。游戏规则如下，注意其与一般玩法可能有不同：

• 有 $2n$ 张牌，其中对于整数 $1 \le i \le n$，牌面为 $i$ 的牌恰好有 $2$ 张。
• 游戏开始时，小 I 和小 J 各拿其中 $n$ 张牌组成双方的初始手牌。
• 维护一个公共牌堆（可以将其看作一个栈），初始没有牌。小 I 与小 J 依次行动，小 I 先手。一次行动时，行动方依次进行以下操作：
  1. 将手牌中的一张牌放在公共牌堆顶；
  2. 若此时公共牌堆中有两张相同的牌，则这两张相同的牌以及在这两张牌之间的所有牌从公共牌堆移到当前行动方手牌中；
  3. 若此时当前行动方没有手牌，则当前行动方失败，另一方胜利。

小 J 是扑克萌新，所以会按照以下策略行动：

• 维护一个队列，初始将 $n$ 张手牌按照一定顺序放入队列中；
• 每次行动时，将队列开头的牌放在公共牌堆顶；
• 若小 J 放入某张牌后公共牌堆中有两张相同的牌，则按照在公共牌堆中自顶到底的顺序将获得的牌放入队列尾。

小 I 通过偷看得到了小 J 的策略以及队列中牌的顺序。现在小 I 不仅想获胜，还想速战速决，用最少的行动次数获胜，但他也是扑克萌新。所以给定小 J 队列中的 $n$ 张牌以及它们的顺序，你需要给出小 I 的策略，使得小 I 能够获胜，同时行动次数最少，或者告诉他这是不可能的。

输入格式

每组数据的第一行一个整数 $n$ 表示牌面的种数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，从队头到队尾的顺序依次描述小 J 队列中的牌。

得到小 J 的 $n$ 张手牌也就得到了小 I 的 $n$ 张手牌，因此不会输入小 I 的手牌。

输出格式

如果小 I 不可能获胜，只需要输出一个整数 -1；否则第一行输出一个整数 $s$，表示你给出的策略中小 I 的行动次数。接下来一行 $s$ 个整数，依次描述每次行动时小 I 从手牌中放入公共牌堆的牌的牌面，两个数之间以一个空格分隔。注意你给出的策略要满足 $s$ 最小。

3
1 3 3

3
2 1 2

1
1

-1

提示

样例解释 1

子任务

对于所有测试数据，$1 \le n \le 3 \times 10^5$，$1 \le a_1,a_2,\cdots, a_n \le n$，且每个整数在序列 $a$ 中至多出现两次。

题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2023-Pre 查看。