dlaud5379   8달 전

(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

한별이는 오늘 학교에서 수열과 순열을 공부했다. 크기가 n인 순열이란 1부터 n까지의 수가 각각 한 번씩 포함된 수열 a1, ..., an을 말한다.

한별이는 특히 아래의 개념에 흥미를 보이고 있다.

  • 순열 <a1, a2, ..., an>에서 어떤 i에 대해 ai > ai+1일 경우, 그 순열이 그 위치에서 하강한다고 한다.
  • 순열 <a1, a2, ..., an>에서 어떤 i에 대해 ai = i일 경우, 그 위치를 그 순열의 고정점이라고 한다.

한별이는 이 개념들을 응용해 자신만의 한별 순열을 만들기로 했다. 크기가 2n인 순열 A = <a1, a2, ..., a2n>이 다음 조건을 만족할 때 A를 한별 순열이라고 한다.

  • A는 정확히 n번 하강하며, 모든 하강은 홀수 위치에서 일어난다. (즉, 모든 i에 대해 a2i-1 > a2i < a2i+1)
  • A는 정확히 n개의 고정점을 가진다.

예를 들어, 순열 <3, 2, 6, 4, 5, 1>은 한별 순열이다.

한별이에게 한별 순열에 대한 이야기를 들은 은하는 한별 순열에서 모든 고정점을 제거하고 남은 수열을 압축해서 순열로 만드는 변환을 떠올렸다. 수열을 압축하면 수열의 각 원소가 수열에서 자신 이하인 원소의 개수로 바뀐다. 예를 들어, 순열 <3, 2, 6, 4, 5, 1>을 변환하면 <3, 2, 6, 4, 5, 1> → <3, 6, 1> → <2, 3, 1>이 된다.

한별이는 변환된 순열에서 원래의 한별 순열을 복원할 수 있을지 궁금해하고 있다. 한별이를 도와주자!

입력

첫째 줄에 변환된 순열의 크기 n이 주어진다. (1 ≤ n ≤ 100 000)

둘째 줄에 변환된 순열을 이루는 n개의 정수가 차례대로 주어진다.

출력

주어진 순열로 변환되는 한별 순열이 존재할 경우, 그 순열을 이루는 2n개의 정수를 차례대로 출력한다. 가능한 순열이 여러 개라면 아무거나 출력한다.

주어진 순열로 변환되는 한별 수열이 존재하지 않을 경우, -1을 출력한다.

댓글을 작성하려면 로그인해야 합니다.