식사 계획 세우기

문제

철수가 사는 KOI 나라에는 $NN$개의 식당이 있다. 각 식당에서는 한 종류의 음식만 판매하는데, $ii$ (1 ≤ i ≤ N)번 식당이 파는 음식의 종류는 $11$보다 크거나 같고 $NN$보다 작거나 같은 정수 $A_{i}A\_i$로 표현할 수 있다. 여러 식당이 같은 종류의 음식을 판매할 수도 있다.

철수는 $NN$개의 식당을 모두 한 번씩 방문하는 식사 계획을 구성하려고 한다. 철수의 식사 계획은 $11$부터 $NN$까지의 정수로 이루어진 순열 $PP$로 표현할 수 있다. 예를 들어 $P=[2,4,3,1]P\; =\; [2,\; 4,\; 3,\; 1]$이라면 철수는 $22$번 식당, $44$번 식당, $33$번 식당, $11$번 식당을 차례대로 방문하는 식사 계획을 세운 것이다. 철수는 같은 종류의 음식을 연속으로 먹고 싶어하지 않기 때문에, 철수의 식사 계획에서 연속한 두 식당은 다른 종류의 음식을 판매해야 한다. 즉, $i=1,\dots ,N-1i\; =\; 1,\; \backslash dots\; ,\; N\; -\; 1$에 대하여 A_{P_i} ≠ A_{P_{i+1}}을 만족해야 하고, 이를 만족하는 식사 계획을 올바른 식사 계획이라고 부르자. 여러분은 올바른 식사 계획으로 가능한 것 중 $PP$가 사전 순으로 가장 앞선 식사 계획을 찾고자 한다.

예를 들어 $N=9N\; =\; 9$개의 식당이 파는 음식의 종류가 $A=[1,1,1,2,2,3,3,4,3]A\; =\; [1,\; 1,\; 1,\; 2,\; 2,\; 3,\; 3,\; 4,\; 3]$로 주어졌다고 하자. 만약 철수의 식사 계획이 $P=[3,4,1,5,6,2,7,8,9]P\; =\; [3,\; 4,\; 1,\; 5,\; 6,\; 2,\; 7,\; 8,\; 9]$라면 식사 계획에서 연속한 두 식당이 서로 다른 종류의 음식을 판매하므로 이는 올바른 식사 계획임을 알 수 있다. 만약 철수의 식사 계획이 $P=[1,4,2,5,6,3,7,8,9]P\; =\; [1,\; 4,\; 2,\; 5,\; 6,\; 3,\; 7,\; 8,\; 9]$라면이 역시 올바른 식사 계획이고, 가능한 식사 계획 중 $PP$가 사전 순으로 가장 앞선다.

다른 예로 $N=3N\; =\; 3$개의 식당이 파는 음식의 종류가 $A=[1,1,1]A\; =\; [1,\; 1,\; 1]$로 주어진다면 어떻게 식사 계획을 세워도 올바른 식사 계획을 세우는 것이 불가능하다는 것을 알 수 있다.

$NN$개의 식당이 파는 음식의 종류가 주어졌을 때, 만약 올바른 식사 계획을 세우는 것이 불가능하다면 $-1-1$을 출력하고, 가능하다면 올바른 식사 계획으로 가능한 것 중 사전 순으로 가장 앞선 $PP$를 출력하는 프로그램을 작성하라.

입력

첫 번째 줄에 KOI 나라의 식당의 수를 나타내는 정수 $NN$이 주어진다.

두 번째 줄에 각 식당이 파는 음식의 종류를 표현하는 $NN$개의 정수 $A_1,\dots ,A_{N}A\_1,\; \backslash dots\; ,\; A\_N$이 공백을 사이에 두고 주어진다.

출력

만약 올바른 식사 계획을 세우는 것이 불가능하다면 $-1-1$을 출력하고, 가능하다면 올바른 식사 계획으로 가능한 것 중 사전 순으로 가장 앞선 $PP$를 공백 하나씩을 사이에 두고 출력하여라.

힌트

사전 순의 정의

길이가 $NN$인 순열 $X_1,X_2,\dots ,X_{N}X\_1,\; X\_2,\; \backslash dots\; ,\; X\_N$이 길이가 $NN$인 순열 $Y_1,Y_2,\dots ,Y_{N}Y\_1,\; Y\_2,\; \backslash dots\; ,\; Y\_N$보다 사전 순으로 앞선다는 것은 아래 조건과 동치이다.

• X_i ≠ Y_i가 성립하는 가장 작은 $ii$ (1 ≤ i ≤ N)에 대해 이다.

9
1 1 1 2 2 3 3 4 3

1 4 2 5 6 3 7 8 9

3
1 1 1

-1