P10672 [MX-S1-T1] Barrier

Original link: 。

You are given a sequence $a$ of length $n$ consisting only of positive integers, and it is guaranteed that $n$ is even. You need to reorder $a$ so that, for every prefix of $a$ whose length is even, the number of distinct values that have appeared is even, or determine that no such reordering exists。 If there are multiple reorderings that satisfy the condition, you may output any one of them。

The first line contains one positive integer $n$, and it is guaranteed that $n$ is even。 The second line contains $n$ positive integers describing the sequence $a$。

If there is no solution, output $-1$. Otherwise, output one line with $n$ integers describing the reordered sequence $a$。 This problem uses a **custom checker** to verify whether your output is correct. If there are multiple reorderings that satisfy the condition, you may output any one of them。

__Sample Explanation 1__ The sets $\{1,3\}$, $\{1,3,3,1\}$, and $\{1,3,3,1,2,4\}$ all have an even number of distinct values。 __Constraints__ __This problem uses bundled subtasks.__ For $100\%$ of the testdata, $2\le n\le 10^5$, $1\le a_i\le n$, and it is guaranteed that $n$ is even。 | Subtask ID | $n\le $ | $a_i\le $ | Points | | ---------- | ------- | --------- | ---- | | $1$ | $10$ | $n$ | $20$ | | $2$ | $20$ | $n$ | $20$ | | $3$ | $10^5$ | $2$ | $20$ | | $4$ | $10^5$ | $10$ | $20$ | | $5$ | $10^5$ | $n$ | $20$ | Translated by ChatGPT 5