아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

순서

면접 대비

시간 제한1초메모리 제한128 MB

요약
각 원소보다 앞에 있는 작은 원소의 개수로부터 원래 순열을 복원하고, 불가능하면 IMPOSSIBLE을 출력합니다.
난이도

보통10점 중 5점

유형
시뮬레이션, 수학
정답자
아직 제출이 없습니다

문제

서로 다른 nn개의 정수로 이루어진 수열 S=(s1,s2,…,sn)S = (s_1, s_2, \dots, s_n)이 있다. 이 수열은 11부터 nn까지의 정수를 한 번씩만 사용한 순열이다. 즉 모든 i≠ji \ne j에 대해 si≠sjs_i \ne s_j이고, 1≤si≤n1 \le s_i \le n이다.

수열 SS로부터 새로운 수열 R=(r1,r2,…,rn)R = (r_1, r_2, \dots, r_n)을 만들 수 있다. 여기서 rir_i는 sis_i보다 앞에 있는 원소들 {s1,s2,…,si−1}\{s_1, s_2, \dots, s_{i-1}\} 중에서 sis_i보다 작은 값의 개수이다.

예를 들어 n=10n = 10이고 S=(6,4,3,5,1,2,7,8,9,10)S = (6, 4, 3, 5, 1, 2, 7, 8, 9, 10)이면 R=(0,0,0,2,0,1,6,7,8,9)R = (0, 0, 0, 2, 0, 1, 6, 7, 8, 9)이다.

어떤 수열 RR이 주어졌을 때, 이 RR을 만들어 낸 원래 수열 SS를 복원하는 프로그램을 작성하여라. RR에 대응하는 SS는 존재한다면 유일하게 결정되지만, 경우에 따라서는 그러한 SS가 존재하지 않을 수도 있다. 예를 들어 n=5n = 5이고 R=(0,2,2,0,1)R = (0, 2, 2, 0, 1)이면 이 RR에 대응하는 SS는 존재하지 않는다.

입력

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 데이터의 개수 TT가 주어진다. 각 테스트 데이터는 두 줄로 이루어진다. 첫째 줄에는 수열의 길이 nn (1≤n≤1001 \le n \le 100)이 주어지고, 둘째 줄에는 수열 RR을 이루는 nn개의 정수 r1,r2,…,rnr_1, r_2, \dots, r_n이 공백으로 구분되어 주어진다.

출력

각 테스트 데이터마다 주어진 RR에 대응하는 수열 SS를 공백으로 구분하여 한 줄에 출력한다. RR로부터 SS를 복원할 수 없으면 그 줄에 IMPOSSIBLE을 출력한다.

예제3

  1. 예제 1

    입력
    3
    10
    0 0 0 2 0 1 6 7 6 9
    10
    0 0 0 0 0 0 0 0 0 0
    12
    0 3 4 5 0 1 2 3 4 5 6 7
    
    예상 출력
    6 4 3 5 1 2 8 9 7 10
    10 9 8 7 6 5 4 3 2 1
    IMPOSSIBLE
    
  2. 예제 2

    입력
    1
    5
    0 1 2 3 4
    
    예상 출력
    1 2 3 4 5
    
  3. 예제 3

    입력
    1
    5
    0 0 0 0 0
    
    예상 출력
    5 4 3 2 1