Background

Original link: https://oier.team/problems/S1A。

Problem Description

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。

Input Format

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$。

Output Format

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。

6
2 3 3 4 1 1

1 3 3 1 2 4

2
1 1

-1

Hint

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。

Translated by ChatGPT 5