최장 증가 부분 수열 역문제

역문제는 이론 컴퓨터과학 연구에서 자주 등장한다. 보통 역문제는 주어진 해가 달성되는 입력을 구성하는 문제로 정의된다. 이 문제에서는 최장 증가 부분 수열의 역문제를 해결해야 한다.

길이 n인 수열 a[1..n]의 증가 부분 수열은 1 ≤ i1 < i2 < ... < ik ≤ n인 a[i1] < a[i2] < ... < a[ik]를 말한다. 최장 증가 부분 수열(LIS) 문제는 주어진 수열에서 원소 수가 최대인 증가 부분 수열을 찾는 문제다.

LIS 문제를 풀 때는 배열 d[1..n]을 구성한다. 여기서 d[i]는 a[i]로 끝나는 a[1..i]의 최장 증가 부분 수열의 길이다.

예를 들어 수열 a = [3, 2, 4, 1, 5, 6]에 대해 구성되는 배열 d는 d = [1, 1, 2, 1, 3, 4]이다.

주어진 배열 d에 대해, LIS 문제를 풀 때 구성되는 배열 d가 주어진 배열과 일치하는 수열 a를 찾아야 한다. 수열 a의 모든 수는 서로 다른 양의 정수이고 1015 이하여야 한다.

첫째 줄에 테스트 예제의 수를 나타내는 양의 정수 t가 주어진다. 다음으로 테스트 예제의 설명이 이어진다.

각 테스트 예제는 두 줄로 설명된다. 첫째 줄에는 수열의 길이를 나타내는 양의 정수 n이 주어진다(1 ≤ n ≤ 300 000). 둘째 줄에는 n개의 양의 정수, 배열 d가 주어진다.

모든 테스트 예제의 n 값의 합은 300 000을 넘지 않는다.

각 테스트 예제에 대해 1015 이하인 n개의 서로 다른 양의 정수를 출력한다. 이 수들이 구하는 수열 a이다. 입력 데이터에는 구하는 수열이 존재한다. 가능한 해가 여러 개라면 아무거나 출력해도 된다.