Problem Description

Player I and Player J are playing a card game called “Train Firing”, also known as “Trailer” and “Kitten Fishing”. The rules are as follows (note that they may differ from the common version):

• There are $2n$ cards. For each integer $1 \le i \le n$, there are exactly $2$ cards with face value $i$.
• At the start of the game, Player I and Player J each take $n$ cards to form their initial hands.
• Maintain a public pile (which can be viewed as a stack), initially empty. Player I and Player J take turns, with Player I going first. In one turn, the current player performs the following operations in order:
  1. Put one card from their hand onto the top of the public pile.
  2. If there are now two identical cards in the public pile, then move these two identical cards and all cards between them from the public pile into the current player’s hand.
  3. If the current player has no cards in hand at this time, then the current player loses and the other player wins.

Player J is a beginner, so he acts according to the following strategy:

• Maintain a queue. Initially, put his $n$ hand cards into the queue in a certain order.
• On each turn, put the card at the front of the queue onto the top of the public pile.
• If after Player J plays a card there are two identical cards in the public pile, then append the obtained cards to the back of the queue in the order from top to bottom of the public pile.

By peeking, Player I knows Player J’s strategy and the order of cards in Player J’s queue. Now Player I not only wants to win, but also wants to win quickly, i.e., win with the minimum number of turns. However, he is also a beginner. Therefore, given the $n$ cards in Player J’s queue and their order, you need to output a strategy for Player I such that Player I can win with the minimum number of turns, or tell him that this is impossible.

Input Format

The first line of each test case contains an integer $n$, denoting the number of distinct face values.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, describing the cards in Player J’s queue from front to back.

Knowing Player J’s $n$ hand cards also determines Player I’s $n$ hand cards, so Player I’s hand will not be given as input.

Output Format

If Player I cannot win, output a single integer -1. Otherwise, output an integer $s$ in the first line, denoting the number of turns taken by Player I in your strategy. Then output a line of $s$ integers, describing in order the face values of the cards that Player I plays from his hand onto the public pile in each turn, separated by one space. Note that your strategy must make $s$ as small as possible.

3
1 3 3

3
2 1 2

1
1

-1

Hint

Sample Explanation 1

Subtasks

For all testdata, $1 \le n \le 3 \times 10^5$, $1 \le a_1,a_2,\cdots, a_n \le n$, and each integer appears at most twice in the sequence $a$.

Source

From the preliminary round of the 2023 Tsinghua University Student Algorithm and Programming Contest and Collegiate Invitational (THUPC2023).

Solutions and other resources can be found at https://github.com/THUSAAC/THUPC2023-Pre.

Translated by ChatGPT 5