← 返回题目列表

AtCoder · arc044_d

D. 后缀数组

中文机器翻译题面 查看原题

問題文

高桥先生喜欢后缀数组构造算法。我每天都在尝试实现不同的后缀数组构造算法。 然而,高桥构建了如此多的后缀数组,以至于他厌倦了构建后缀数组。 因此,高桥决定在给定排列的后缀数组中找到具有该排列的最小词典字符串。

但是,2字符串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,后缀数组是对每个i从第i个字符到S末尾按顺序排列的字符串列表,并且该字符串的每个元素对应的i按顺序排列,即按字典顺序排列。 例如,字符串 ABACABA 的后缀数组为 [7,5,1,3,6,2,4]。

给定长度为 N 的排列,找到在后缀数组中具有该排列的仅由大写字母组成的字典顺序最小的字符串。如果不存在这样的字符串,则打印 -1。


入力

输入将以以下格式从标准输入给出。

N
A_1 A_2 ... A_N
  • 1 行包含一个整数 给出了N(1 ≦ N ≦ 10^6)给出。
  • 2 行包含一个整数列。 给出了A_1,...,A_N(1 ≦ A_1,...,A_N ≦ N)。这些N整数是多少?2保证彼此不同。 输出后缀数组中具有

出力

順列A_1,...,A_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