问题描述

高桥君喜欢构建后缀数组的算法。他每天都在实现和研究各种后缀数组的构建算法。然而，高桥君由于过度构建后缀数组而感到厌倦，所以决定对给定的排列求出按字典顺序最小的能够构成该排列的字符串。

给定两个字符串$X_1,X_2,...,X_s$和$Y_1,Y_2,...,Y_t$，我们认为按字典顺序$X<Y$成立，当且仅当满足以下条件之一：

• 存在整数$i(1≤i≤min(s,t))$，使得对于满足$1≤j≤i-1$的任意整数$j$，都有$X_j=Y_j$且$X_i<Y_i$。
• 对于任意整数$i(1≤i≤min(s,t))$，都有$X_i=Y_i$且$s<t$。

另外，对于给定的字符串$S$，它的后缀数组是指将字符串$S$的每个位置到末尾的子串按照字典顺序排序，并将对应的位置依次排列起来的结果。例如，字符串ABACABA的后缀数组是[7,5,1,3,6,2,4]。

现在给定一个长度为$N$的排列，请求出按字典顺序最小的，只由大写英文字母组成且能够构成该排列的字符串。如果不存在这样的字符串，则输出-1。

输入

输入从标准输入中以以下形式给出：

$N$ $A_1 A_2 ... A_N$

• 第一行包含一个整数$N(1≤N≤10^6)$，表示排列的长度。
• 第二行包含$N$个整数$A_1,...,A_N(1≤A_1,...,A_N≤N)$，表示给定的排列。保证这$N$个数两两互不相同。

输出

请输出满足条件的按字典顺序最小的字符串。

在最后输出一个换行符。(修改于21:40)

输入样例1

7
7 5 1 3 6 2 4

输出样例1

ABACABA

满足条件的字符串还有其他多个，比如$CXHZBWA$，但字典序最小的是$ABACABA$。

输入样例2

12
7 1 9 10 2 4 3 6 12 5 11 8

输出样例2

BDEDGFAHCCGG