Arrange Books Without Adjacent Duplicates

You are given n books, each belonging to a certain series. Your task is to determine whether it is possible to arrange these books in a row such that no two adjacent books come from the same series.

If an arrangement is possible, print one valid ordering of the book series names separated by a single space. Otherwise, print -1.

This problem can be interpreted using a greedy strategy. A necessary condition for the existence of a valid arrangement is that the maximum frequency \( f_{\max} \) of any series satisfies \( f_{\max} \leq \lceil n/2 \rceil \). Use appropriate data structures (like a max-heap) to achieve an efficient solution.

inputFormat

The input is given from stdin as follows:

1. The first line contains an integer n representing the number of books.
2. The second line contains n strings separated by spaces, where each string represents the series name of a book.

outputFormat

Output to stdout a single line. If a valid arrangement exists, print the arrangement (book series names separated by a single space). If no valid arrangement exists, print -1.

3
HarryPotter HarryPotter HarryPotter

-1