Problem Description

Takahashi loves constructing suffix arrays. He plays with various algorithms to construct suffix arrays every day. However, he has grown tired of constructing suffix arrays because he has done it too much. Now, Takahashi has decided to find the lexicographically smallest string that has a given permutation as its suffix array.

For two strings \( X_1,X_2,...,X_s \) and \( Y_1,Y_2,...,Y_t \), \( X < Y \) in lexicographical order if one of the following conditions is met:

• There exists an integer \( i \) ( \( 1 \leq i \leq \min(s,t) \) ) such that for any integer \( j \) satisfying \( 1 \leq j \leq i-1 \), \( X_j = Y_j \) and \( X_i < Y_i \).
• For any integer \( i \) ( \( 1 \leq i \leq \min(s,t) \) ), \( X_i = Y_i \) and \( s < t \).

Given a string \( S \), its suffix array is a list of indices \( i \) such that the substrings starting from the \( i \)-th character to the end of the string are sorted lexicographically. For example, the suffix array of the string "ABACABA" is \[7,5,1,3,6,2,4\].

Given a permutation of length \( N \), find the lexicographically smallest string consisting of uppercase English letters that has this permutation as its suffix array. If no such string exists, output -1 instead.

Input Format

The input is given from the standard input in the following format:

\( N \) \( A_1\ A_2\ ...\ A_N \)

• The first line contains an integer \( N \) ( \( 1 \leq N \leq 10^6 \) ).
• The second line contains a sequence of integers \( A_1,...,A_N \) ( \( 1 \leq A_1,...,A_N \leq N \) ). It is guaranteed that all \( N \) integers are distinct.

Output Format

Output the lexicographically smallest string that has the permutation \( A_1,...,A_N \) as its suffix array.

End the output with a newline. (corrected at 21:40)

Sample Input and Output

Sample Input #1

7
7 5 1 3 6 2 4

Sample Output #1

ABACABA

Sample Input #2

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

Sample Output #2

BDEDGFAHCCGG

Notes/Hints

Sample Explanation 1

Other strings that satisfy the conditions include "CXHZBWA", but output the lexicographically smallest "ABACABA".

见题面 Input 部分

见题面 Output 部分