[EC Final 2022] Minimum Suffix

**【题目描述】** 对于长度为 $n$ 的字符串 $s$，如果 $s[x\ldots j]$ 是 $s[1\ldots j]$ 的最小后缀，则我们定义 $p_j = x$，其中 $j=1,\ldots, n$。（后缀是字符串的最小后缀，如果它在字典序上小于该字符串的任何其他后缀。） 你需要从 $p_1,\ldots, p_n$ 中恢复出 $s$。如果存在多个答案，则找出字典序最小的那个。 **【输入格式】** 第一行包含一个整数 $T$（$1\le T\le 10^5$），表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$（$1\le n\le 3\times 10^6$），表示 $s$ 的长度。接下来的一行包含 $n$ 个整数 $p_1,\ldots, p_n$（$1\le p_i\le i$，$1\le i\le n$）。 保证所有测试用例中 $n$ 的总和不超过 $3\times 10^6$。 **【输出格式】** 对于每个测试用例，输出一行。如果没有解决方案，则输出 $-1$。否则，输出字典序最小的 $s$。$s$ 中的字符由正整数表示。较小的整数表示字典序较小的字符。 **【提示说明】** 本题输入输出规模较大，建议使用快速的输入输出方式。 翻译来自于：[ChatGPT](https://chatgpt.com/)。

For a string $s$ of length $n$, we define $p_j = x$ if $s[x\ldots j]$ is the minimum suffix of $s[1\ldots j]$, for all $j=1,\ldots, n$. (A suffix is the minimum suffix of a string if it is lexicographically smaller than any other suffix of that string.) You are to recover $s$ from $p_1,\ldots, p_n$. If there are multiple answers, find the lexicographically smallest one.

The first line contains a single integer $T$ ($1\le T\le 10^5$) representing the number of test cases. For each test case, the first line contains a single integer $n$ ($1\le n\le 3\times 10^6$) representing the length of $s$. The next line contains $n$ integers $p_1,\ldots, p_n$ ($1\le p_i\le i$ for all $1\le i\le n$). It is guaranteed that the sum of $n$ over all test cases does not exceed $3\times 10^6$.

For each test case, output one line. If there is no solution, output $-1$. Otherwise, output the lexicographically smallest $s$. Characters of $s$ are represented by positive integers. Smaller integers represent smaller characters in the lexicographical order.

6
3
1 1 1
3
1 1 2
3
1 1 3
3
1 2 1
3
1 2 2
3
1 2 3

1 2 2
-1
1 2 1
1 1 2
2 1 2
1 1 1

As the input/output can be huge, it is recommended to use fast input/output methods.