Suffix Array Reconstruction

Given a text $s[1..n]$ of length $n$, form all of its suffixes

$s[1..n],\ s[2..n],\ \ldots,\ s[n..n]$

and sort them lexicographically to obtain the sorted list

$s[p(1)..n],\ s[p(2)..n],\ \ldots,\ s[p(n)..n].$

The sequence $p(1), p(2), \ldots, p(n)$ is called the suffix array of $s$. For example, if $s = \texttt{abbaabab}$, sorting all suffixes lexicographically gives

aabab, ab, abab, abbaabab, b, baabab, bab, bbaabab

so the suffix array is $4, 7, 5, 1, 8, 3, 6, 2$.

Your task is the inverse. Given a sequence $p(1), p(2), \ldots, p(n)$ (a permutation of $1$ through $n$), decide whether there exists a text over lowercase English letters whose suffix array is exactly this sequence, and if so reconstruct such a text.

The first line contains the number of test cases $t$ ($1 \le t \le 100$). Each test case consists of two lines: the first contains the length $n$ ($1 \le n \le 500000$) of both the text and the array, and the second contains the $n$ integers $p(1), p(2), \ldots, p(n)$. It is guaranteed that $1 \le p(i) \le n$ and that no value occurs twice (so $p$ is a permutation of $1..n$). The total size of the input does not exceed 50 MB.

For each test case, if some text over lowercase English letters (a–z) has $p$ as its suffix array, output the lexicographically smallest such text on its own line. Otherwise output -1.