Inverse Longest Increasing Subsequence

Inverse problems often appear in theoretical computer science research. Usually an inverse problem is stated as follows: given a solution, construct a set of inputs on which this solution is attained. In this problem you must solve the inverse problem for the longest increasing subsequence.

Recall that an increasing subsequence of a sequence a[1..n] of length n is a sequence a[i1] < a[i2] < ... < a[ik], where 1 ≤ i1 < i2 < ... < ik ≤ n. The longest increasing subsequence (LIS) problem is to find an increasing subsequence of a given sequence with the maximum number of elements.

When solving the LIS problem, an array d[1..n] is built, where d[i] is the length of the longest increasing subsequence of a[1..i] that ends at a[i].

For example, for the sequence a = [3, 2, 4, 1, 5, 6] the array d built is d = [1, 1, 2, 1, 3, 4].

Given an array d, find a sequence a such that when the LIS problem is solved, the array d built coincides with the given one. All numbers in the sequence a must be distinct positive integers not exceeding 1015.

The first line contains a positive integer t, the number of test cases in the input. The descriptions of the test cases follow.

Each test case is described by two lines. The first line contains a positive integer n, the length of the sequence (1 ≤ n ≤ 300 000). The second line contains n positive integers, the array d.

The sum of the values of n over all test cases does not exceed 300 000.

For each test case, output n distinct positive integers not exceeding 1015, the sought sequence a. The input data is such that the sought sequence exists. If there are several possible solutions, you may output any of them.