4.2 Map ka map ka map....
(RankList for this Question)
Score: 15pts
Time Limit: 5.00 sec
You have an array B representing the frequencies of elements, and your goal is to find the smallest possible array A such that:
- The elements of A are between 1 and 10^5.
- The frequency array of A is equal to B.
If it's not possible to create such an array A, print -1.
Note: In comparing two arrays X and Y, the lexicographically smaller one is determined by comparing the elements at the first index where they differ, with the smaller element indicating the smaller array.

For example, if A = [4, 7, 4, 11, 2, 7, 7], the frequency array B = [2, 3, 2, 1, 1, 3, 3] so
The frequency array of A is the array B of size N such that B[i] = frequency of element A[i] in A.

Constraints
1 ≤ T ≤ 10^5 (number of test cases)
1 ≤ N ≤ 10^5 (size of the array)
1 ≤ Bi ≤ 10^5 (frequency array elements)
The sum of N over all test cases won't exceed 10^6.

Input Format
The first line contains an integer T, the number of test cases.
For each test case:
The first line contains an integer N, the size of the array.
The second line contains N space-separated integers, which make up the frequency array B.

Output Format
For each test case, output the lexicographically smallest array A of size N that matches the given frequency array B. If no such array exists, print -1.

Example 1
Input:
5
5
2 3 3 3 2
5
1 1 1 1 1
5
5 5 5 5 5
3
1 2 4
8
1 3 2 3 2 2 2 3

Output:
1 2 2 2 1
1 2 3 4 5
1 1 1 1 1
-1
1 2 3 2 3 4 4 2

Explanation:
Test case 1:
- The lexicographically smallest array A having the given frequency array B is A = [1, 2, 2, 2, 1].
- The element 1 (A1) and 5 (A5) have frequency 2, while 2 (A2), 3 (A3), and 4 (A4) have frequency 3.

Test case 2:
- The lexicographically smallest array A having the given frequency array B is A = [1, 2, 3, 4, 5].
- Each element in A has frequency 1.

Test case 3:
- The lexicographically smallest array A having the given frequency array B is A = [1, 1, 1, 1, 1].
- Each element in A has frequency 5.

Test case 4:
- No possible array A exists having the given frequency array B.

Log In to solve the Question