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

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

대기줄 복원

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

요약
각 사람이 줄의 어느 자리에 들어섰다는 기록으로 해산 직전 각자의 최종 위치를 구합니다.
난이도

보통10점 중 5점

유형
세그먼트 트리
정답자
아직 제출이 없습니다

문제

건설 노동자 아드리안은 오늘 할 일이 많지 않아, 가게 앞 대기줄을 연구하는 자료를 모으고 있다.

아드리안은 근처 가게 앞 대기줄을 지켜보며, 차례로 도착하는 사람이 줄의 어느 위치에 섰는지를 기록한다. 하루가 시작될 때 줄에는 아무도 없었다. 새로 온 사람이 반드시 줄 맨 뒤에 서는 것은 아니다. 누군가와 미리 약속했거나, 돈을 주었거나, 무언가를 건넸거나, 다른 방법을 써서 줄의 어느 위치든 끼어들 수 있다. 한 번 줄에 선 사람은 정오까지 줄을 떠나지 않았고, 정오가 되자 오늘 가게가 열지 않는다는 사실이 밝혀져 모두 흩어졌다.

아드리안은 자신의 기록만으로, 사람들이 흩어지기 직전의 줄 배치를 복원할 수 있는지 궁금하다.

입력

첫 줄에 테스트 세트의 수 ZZ (1≤Z≤101 \le Z \le 10)가 주어진다. 이어서 각 테스트 세트가 차례로 주어진다.

각 세트의 첫 줄에는 아침부터 정오까지 줄에 선 사람의 수를 나타내는 자연수 NN (1≤N≤1000001 \le N \le 100000)이 주어진다. 둘째 줄에는 NN개의 정수 X1,X2,…,XNX_1, X_2, \dots, X_N (0≤Xi<i0 \le X_i < i, 1≤i≤N1 \le i \le N)이 주어진다.

XiX_i가 00이면 ii번째 사람은 줄의 맨 앞에 섰다는 뜻이다. 그렇지 않으면 ii번째 사람은, 자신이 도착한 순간에 줄의 앞에서부터 세어 XiX_i번째였던 사람의 바로 뒤에 섰다는 뜻이다.

출력

각 세트마다 한 줄에 NN개의 정수를 공백 하나로 구분하여 출력한다. ii번째 정수는 ii번째로 줄에 들어온 사람의 최종 위치여야 한다. 줄의 맨 앞에 선 사람의 위치는 11, 그 뒤는 22와 같이 매긴다.

예제3

  1. 예제 1

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

    입력
    1
    1
    0
    
    예상 출력
    1
    
  3. 예제 3

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