Even Distinct Prefix Reordering

Given an even-length sequence of positive integers \(a_1,a_2,\dots,a_n\) (with \(n\) even), reorder the sequence such that for every even-length prefix, the number of distinct integers is even. Formally, if \(P_k = (a_1,a_2,\dots,a_k)\) for even \(k\), then \(|\{a_1,a_2,\dots,a_k\}|\) is even. If such a rearrangement exists, output any valid reordering; otherwise, output -1.

Note: The input guarantees that all numbers are positive integers.

inputFormat

The first line contains an even integer (n) (the length of the sequence). The second line contains (n) positive integers (a_1,a_2,\dots,a_n) separated by spaces.

outputFormat

If a valid reordering exists, output the rearranged sequence as (n) space-separated integers in one line. If no valid rearrangement exists, output -1.

sample

2
1 2

1 2