철수가 사는 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, \dots , 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\)를 출력하는 프로그램을 작성하라.

Hint.

사전 순의 정의

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

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

• \(1 \le N \le 300\,000\)
• \(1 \le A_i \le N\)

첫 번째 줄에 KOI 나라의 식당의 수를 나타내는 정수 \(N\)이 주어진다.

두 번째 줄에 각 식당이 파는 음식의 종류를 표현하는 \(N\)개의 정수 \(A_1, \dots , A_N\)이 공백을 사이에 두고 주어진다.

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

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2022 > 2차 대회 > 고등부 2번