Background

Xiao E has gotten tired of Meow Meow Meow, so they decided to try a different match-elimination game. However, Xiao E found that most elimination games on the market have almost the same rules. For example, this game differs from Meow Meow Meow by only one character. Although changing one character makes it a new game, it still feels a bit lacking.

Problem Description

This game has one deck and $n$ stacks. The goal is to eliminate all cards following the rules. Initially, there are $m$ cards in the deck, whose patterns from top to bottom are $a_1, a_2, \cdots, a_m$. There are $k$ kinds of patterns in total, numbered from $1$ to $k$. In the deck, the number of cards of each pattern is even. Initially, all stacks are empty. There are two operations in this game:

• Choose a stack and put the top card of the deck onto the top of that stack. If after doing so, the top two cards of this stack have the same pattern, then these two cards will be eliminated automatically.

• Choose two different stacks. If the cards at the top of these two stacks have the same pattern, then you may eliminate these two cards. If they are different, then nothing happens.

After observing many times, Xiao E found that it is always the case that $n = 2$ and $k = m / 2$, i.e. there are only two stacks and each pattern has exactly $2$ cards. Even so, Xiao E still cannot clear the game. Please help Xiao E design a strategy for the game, i.e. output a corresponding sequence of operations so that Xiao E can eliminate all cards.

Input Format

The first line contains a positive integer $m$.

The second line contains $m$ positive integers, denoting $a_1, a_2, \cdots, a_m$.

It is guaranteed that each integer in $1 \sim m / 2$ appears exactly twice in the sequence.

Output Format

This problem uses special judge.

If there is no solution, output one line No solution..

If there is a solution, output Cleared. in the first line. In the second line output a positive integer $op$, the number of operations. You need to ensure $m \le op \le 2m$.

Then output a string of length $op$, one character per operation. Each character is a non-negative integer not exceeding $2$, representing the operation performed in order. If it is 1 or 2, it means performing the first operation and choosing stack $1$ or stack $2$. If it is 0, it means performing the second operation. Since there are only two stacks, you do not need to output extra information to specify which two stacks you choose.

4
1 2 1 2

Cleared.
5
12202

Hint

Explanation of Sample 1

The figure below shows the initial state.

The figure below shows the result after the first two operations.

The figure below shows the result after the third and fourth operations.

The figure below shows the result after the fifth operation.

Constraints

• It is guaranteed that $2 \le m \le 1500$ and $m$ is even.
• It is guaranteed that $1 \le a_i \le m / 2$, and each number appears exactly twice in the sequence.

Scoring

Your first output line must be identical to the standard answer.

If there is a solution, and after performing all operations in order, the deck is empty and all stacks are empty, then your answer is considered correct.

Postscript

The following part is unrelated to this problem.

In fact, the person who complained that the statement of Meow Meow Meow II was too long was Xiao E themself. In the original statement, the background and description were as follows:

【Background】

Xiao E has gotten tired of Meow Meow Meow, so they decided to try a different match-elimination game. However, Xiao E found that most elimination games on the market have almost the same rules. For example, this game differs from Meow Meow Meow only slightly. Although changing one character makes it a new game, it still feels a bit lacking.

【Description】

This game has one deck and $n$ stacks from which elements can be removed from the bottom. The goal is to eliminate all cards following the rules. Initially, there are $m$ cards in the deck, whose patterns from top to bottom are $a_1, a_2, \cdots, a_m$. There are $k$ kinds of patterns in total, numbered from $1$ to $k$. In the deck, the number of cards of each pattern is even. Initially, all stacks are empty. There are two operations in this game:

• Choose a stack and put the top card of the deck onto the top of that stack.

• Choose two different stacks. If the cards at the bottom of these two stacks have the same pattern, then you may eliminate these two cards, and the cards that were originally above the bottom will become the new bottom. If they are different, then nothing happens.

After observing many times, Xiao E found that it is always the case that $n = 2$ and $k = m / 4$, and each pattern has exactly $4$ cards. Even so, Xiao E still cannot clear the game. Please help Xiao E design a strategy for the game, i.e. output a corresponding sequence of operations so that Xiao E can eliminate all cards.

Source

From the finals of THUPC2023, Tsinghua University Student Algorithm and Programming Contest & Collegiate Invitational Contest (THUPC2023).

Resources such as solutions can be found at https://github.com/THUSAAC/THUPC2023.

Translated by ChatGPT 5