철수가 사는 KOI 나라에는 N개의 식당이 있다.

각 식당에서는 한 종류의 음식만 판매하는데, i (1 ≤ i ≤ N)번 식당이 파는 음식의 종류는 1보다 크거나 같고 N보다 작거나 같은 정수 A_i로 표현할 수 있다.

여러 식당이 같은 종류의 음식을 판매할 수도 있다.

철수는 N개의 식당을 모두 한 번씩 방문하는 식사 계획을 구성하려고 한다.

철수의 식사 계획은 1부터 N까지의 정수로 이루어진 순열 P로 표현할 수 있다.

예를 들어 P = [2, 4, 3, 1]이라면 철수는 2번 식당, 4번 식당, 3번 식당, 1번 식당을 차례대로 방문하는 식사 계획을 세운 것이다.

철수는 같은 종류의 음식을 연속으로 먹고 싶어하지 않기 때문에, 철수의 식사 계획에서 연속한 두 식당은 다른 종류의 음식을 판매해야 한다.

즉, i = 1, ···, N − 1에 대하여 A_{p_i} ≠ A_{p_{i+1}}을 만족해야 하고, 이를 만족하는 식사 계획을 올바른 식사 계획이라고 부르자.

여러분은 올바른 식사 계획으로 가능한 것 중 P가 사전순으로 가장 앞선 식사 계획을 찾고자 한다.

예를 들어 N = 9개의 식당이 파는 음식의 종류가 A = [1, 1, 1, 2, 2, 3, 3, 4, 3]로 주어졌다고 하자.

만약 철수의 식사 계획이 P = [3, 4, 1, 5, 6, 2, 7, 8, 9] 라면 식사 계획에서 연속한 두 식당이 서로 다른 종류의 음식을 판매하므로 이는 올바른 식사 계획임을 알 수 있다.

만약 철수의 식사 계획이 P = [1, 4, 2, 5, 6, 3, 7, 8, 9] 이라면 이 역시 올바른 식사 계획이고, 가능한 식사 계획 중 P가 사전 순으로 가장 앞선다.

다른 예로 N = 3개의 식당이 파는 음식의 종류가 A = [1, 1, 1]로 주어진다면

어떻게 식사 계획을 세워도 올바른 식사 계획을 세우는 것이 불가능하다는 것을 알 수 있다.

N개의 식당이 파는 음식의 종류가 주어졌을 때, 만약 올바른 식사 계획을 세우는 것이 불가능하다면 -1을 출력하고,

가능하다면 올바른 식사 계획으로 가능한 것 중 사전 순으로 가장 앞선 P를 출력하는 프로그램을 작성하라.

[사전 순의 정의]

길이가 N인 순열 X_1, X_2, ···, X_N이 길이가 N인 순열 Y_i, Y_2, ···, Y_N 보다 사전 순으로 앞선다는 것은 아래 조건과 동치이다.

식사 계획 세우기 timer 3초 memory 256MB

식사 계획 세우기 3초 256MB