60056 식사 계획 세우기 Platinum III

문제

N개의 식당이 있고, 각 식당은 음식 종류 A_i를 판다. 식당을 방문하는 순열을 구하되, 연속 두 식당이 같은 음식을 팔지 않아야 한다. 사전순으로 가장 빠른 순열을 구하시오. 불가능하면 -1.

입력

첫째 줄에 N (1 ≤ N ≤ 300,000)이 주어진다. 둘째 줄에 A_1, …, A_N이 주어진다.

출력

사전순 최소 순열 또는 -1.