write a go solution for D. Local Constructiontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output  An element b_i (1<=i<=m) in an array b_1,b_2,ldots,b_m is a local minimum if at least one of the following holds:   2<=i<=m-1 and b_i<b_i-1 and b_i<b_i+1, or  i=1 and b_1<b_2, or  i=m and b_m<b_m-1. Similarly, an element b_i (1<=i<=m) in an array b_1,b_2,ldots,b_m is a local maximum if at least one of the following holds:   2<=i<=m-1 and b_i>b_i-1 and b_i>b_i+1, or  i=1 and b_1>b_2, or  i=m and b_m>b_m-1. Note that local minima and maxima are not defined for arrays with only one element.There is a hidden permutation^∗ p of length n. The following two operations are applied to permutation p alternately, starting from operation 1, until there is only one element left in p:  Operation 1 — remove all elements of p which are not local minima.  Operation 2 — remove all elements of p which are not local maxima. More specifically, operation 1 is applied during every odd iteration, and operation 2 is applied during every even iteration, until there is only one element left in p.For each index i (1<=i<=n), let a_i be the iteration number that element p_i is removed, or -1 if it was never removed.It can be proven that there will be only one element left in p after at most ceil(log_2n) iterations (in other words, a_i<=ceil(log_2n)).You are given the array a_1,a_2,ldots,a_n. Your task is to construct any permutation p of n elements that satisfies array a.^∗A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (n=3 but there is 4 in the array). InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^4). The description of the test cases follows. The first line of each test case contains a single integer n (2<=n<=2*10^5) — the number of elements in permutation p.The second line of each test case contains n integers a_1,a_2,ldots,a_n (1<=a_i<=ceil(log_2n) or a_i=-1) — the iteration number that element p_i is removed.It is guaranteed that the sum of n over all test cases does not exceed 2*10^5. It is guaranteed that there exists at least one permutation p that satisfies array a.OutputFor each test case, output n integers representing the elements of the permutation satisfying array a.If there are multiple solutions, you may output any of them.ExampleInput731 1 -151 -1 1 2 183 1 2 1 -1 1 1 271 1 1 -1 1 1 151 1 1 1 -15-1 1 1 1 15-1 1 2 1 2Output3 2 1
4 3 5 1 2
6 7 2 4 3 8 5 1
6 5 2 1 3 4 7
5 4 3 2 1
1 2 3 4 5
4 5 2 3 1NoteIn the first test case, operations will be applied to permutation [3,2,1] as follows:  The only local minimum in [3,2,1] is 1. Hence, elements 3 and 2 are removed. There is only one remaining element; hence the process terminates. This satisfies array a=[1,1,-1] as both p_1 and p_2 were removed on iteration number 1, while p_3 was not removed.In the second test case, operations will be applied to permutation p=[4,3,5,1,2] as follows:  The local minima in [4,3,5,1,2] are 3 and 1. Hence, elements 4, 5, and 2 are removed.  The only local maximum in [3,1] is 3. Hence, element 1 is removed. There is only one remaining element; hence the process terminates. This satisfies array a=[1,-1,1,2,1] as elements p_1=4, p_3=5, and p_5=2 were removed on iteration 1, element p_4=1 was removed on iteration 2, and element p_2=3 was not removed.In the third test case, operations will be applied on permutation [6,7,2,4,3,8,5,1] as follows:  The local minima in [6,7,2,4,3,8,5,1] are 6, 2, 3, and 1. Hence, elements 7, 4, 8, and 5 are removed.  The local maxima in [6,2,3,1] are 6 and 3. Hence, elements 2 and 1 are removed.  The only local minimum in [6,3] is 3. Hence, element 6 is removed. There is only one remaining element; hence the process terminates. In the fourth test case, one permutation satisfying the constraints is [6, 5, 2, 1, 3, 4, 7]. 1 is the only local minimum, so only it will stay after the first iteration. Note that there are other valid permutations; for example, [6, 4, 3, 1, 2, 5, 7] would also be considered correct.. Output only the code with no comments, explanation, or additional text.