AT_arc044_d.[ARC044D] suffix array

高桥君非常喜欢后缀数组的构建算法。他每天都会实现各种各样的后缀数组构建算法来玩。不过，高桥君构建了太多的后缀数组，已经感到厌倦了。因此，他决定，对于给定的一个排列，要求出一个仅由大写英文字母组成的、字典序最小的字符串，使得该字符串的后缀数组恰好等于给定的排列。

这里，给定两个字符串 $X_1,X_2,\ldots,X_s$ 和 $Y_1,Y_2,\ldots,Y_t$，我们定义 $X < Y$（即 $X$ 的字典序小于 $Y$）当且仅当满足以下两个条件之一：

• 存在某个整数 $i\ (1 \leq i \leq \min(s,t))$，使得对于任意 $j\ (1 \leq j \leq i-1)$ 都有 $X_j=Y_j$，且 $X_i < Y_i$；
• 对于任意 $i\ (1 \leq i \leq \min(s,t))$ 都有 $X_i=Y_i$，且 $s < t$。

对于给定的字符串 $S$，其后缀数组定义为：对于每个 $i$，枚举从 $S$ 的第 $i$ 个字符到末尾的所有后缀字符串，将这些后缀按字典序排序，然后输出这些后缀在原字符串中的起始位置 $i$ 的排列。例如，字符串 $ABACABA$ 的后缀数组为 $[7,5,1,3,6,2,4]$。

现在给定一个长度为 $N$ 的排列，请你求出一个仅由大写英文字母组成的、字典序最小的字符串，使其后缀数组等于该排列。如果不存在这样的字符串，则输出 $-1$。

输入通过标准输入给出，格式如下：

$N$
$A_1\ A_2\ \ldots\ A_N$

• 第 $1$ 行包含一个整数 $N\ (1 \leq N \leq 10^6)$。
• 第 $2$ 行包含一个长度为 $N$ 的整数序列 $A_1,\ldots,A_N\ (1 \leq A_1,\ldots,A_N \leq N)$，保证这 $N$ 个整数两两不同。

输出一个仅由大写英文字母组成的、字典序最小的字符串，使其后缀数组等于给定的排列 $A_1,\ldots,A_N$。如果不存在这样的字符串，则输出 $-1$。

输出末尾需要换行。

样例解释 1

满足条件的字符串还有 $CXHZBWA$ 等，但字典序最小的是 $ABACABA$，因此输出 $ABACABA$。

由 ChatGPT 4.1 翻译