Lexicographically Maximum Suffix String Construction

Given an integer n and a sequence of n integers \(a_1, a_2, \ldots, a_n\) (with 1-indexing) satisfying the following necessary condition:

• \(a_1 = 1\), and for each \(i \ge 1\), \(a_{i+1}\) must be either 1 or \(a_i + 1\).

Your task is to construct a length-n string \(w\) whose characters are integers in the set \(\{1,2,\ldots,n\}\) (where the natural order is defined as \(1 < 2 < \cdots < n\)) such that for every \(i\) (\(1 \le i \le n\)), if you consider the prefix \(w[1\ldots i]\), then the lexicographically maximum suffix of this prefix has length exactly \(a_i\). If no such string exists, report no solution.

The lexicographically maximum suffix of a string \(s\) (where \(s = s_1s_2\ldots s_i\)) is defined as follows. Consider all suffixes \(s[j\ldots i]\) for \(1 \le j \le i\). Let \(m(i)\) be the maximum character in \(s[1\ldots i]\) and let \(k\) be the largest index such that \(s_k = m(i)\). Then the lexicographically maximum suffix is \(s[k\ldots i]\) and its length is \(i-k+1\). In other words, the requirement is that for every \(i\): \[ i - k + 1 = a_i \quad \text{where} \quad k = \max\{j \;|\; 1 \le j \le i \text{ and } s_j = \max(s_1,s_2,\ldots,s_i)\}. \]

Additional requirement: Among all solutions satisfying the condition, you must choose the lexicographically maximum string \(w\) (when compared character by character from left to right). Note that a new occurrence of the current maximum (or a higher value) resets the maximum suffix length to 1.

Observation and construction strategy:

• For the first character, since \(a_1=1\) (and it is the only character in the prefix), you may choose any digit in \(\{1,2,\ldots,n\}\). To maximize the overall lexicographical order, choose \(w_1 = n\). This makes the current maximum \(M = n\).
• For every subsequent position \(i\) (\(2 \le i \le n\)):
  • If \(a_i = a_{i-1}+1\), then the maximum in the prefix is not updated. Hence, the new character must be strictly less than the current maximum \(M\). To keep \(w\) lexicographically maximum, set \(w_i = M - 1\) (it is easy to see this is optimal because digits can be repeated and we want the highest possible value that is less than \(M\)).
  • If \(a_i = 1\), then a new occurrence of a digit at least as high as the current maximum must occur. To maximize lexicographical order, choose \(w_i = n\) (which is \(\ge M\)); subsequently update \(M\) to \(w_i\) (note that if \(M\) was already \(n\), it remains \(n\)).
• If at any position \(a_i\) is not either \(a_{i-1}+1\) or 1 (or if \(a_1 \neq 1\)), then no solution exists.

Input format:

The input begins with a single integer T, indicating the number of test cases. For each test case, the first line contains an integer n. The second line contains n space-separated integers \(a_1, a_2, \ldots, a_n\).

Output format:

For each test case, if a valid string \(w\) exists, output n space-separated integers representing \(w_1, w_2, \ldots, w_n\). If no valid \(w\) exists, output -1.

inputFormat

The first line contains a single integer T denoting the number of test cases.

For each test case:

• The first line contains an integer n.
• The second line contains n space-separated integers \(a_1, a_2, \ldots, a_n\).

outputFormat

For each test case, output one line containing the answer: if a valid string exists, print n space-separated integers representing \(w_1, w_2, \ldots, w_n\); otherwise, print -1.

sample

2
3
1 2 3
3
1 1 2

3 2 2
3 3 2

</p>